leetcode之动态规划刷题总结5_动态规划中fu+1(xu+1)=0是什么意思

leetcode之动态规划刷题总结5

1-两个字符串的最小ASCII删除和
题目链接：题目链接戳这里！！！

思路：动态规划
dp[i][j]表示以i-1结尾的字符串s1和以j-1结尾的字符串s2保持相同所删除的最小ASCII字符。

初始化dp数组
如果其中一个为空串，则为了保持二者相同，需要删除另一个的全部字符。

如果s1.charAt(i-1)==s2.charAt(j-1)，则不需要删除，递推式如下：
dp[i][j] = dp[i-1][j-1]
否则，需要删除两个其中一个ASCII小的，递推式入下：
dp[i][j] = Math.min(dp[i-1][j]+(s1.charAt(i-1)), dp[i][j-1]+(s2.charAt(j-1))) ;

AC代码如下：

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int [][] dp = new int [s1.length()+1][s2.length()+1] ;
        for(int i=1; i<=s1.length(); i++){
            dp[i][0] = dp[i-1][0] + s1.charAt(i-1) ;
        }
        for(int j=1; j<=s2.length(); j++){
            dp[0][j] = dp[0][j-1] + s2.charAt(j-1) ;
        }
        for(int i=1; i<=s1.length(); i++){
            for(int j=1; j<=s2.length(); j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] ;
                }else{
    dp[i][j] = Math.min(dp[i-1][j]+(s1.charAt(i-1)), dp[i][j-1]+(s2.charAt(j-1))) ;
                }
            }
        }
        return dp[s1.length()][s2.length()] ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2-删除并获得点数
题目链接：题目链接戳这里！！！

思路：将nums数组变成每个数字的总和值，然后就变成了打家劫舍问题，每次只能在偷与不偷之间取舍。

class Solution {
    public int deleteAndEarn(int[] nums) {
        int [] value = new int [10001] ;
        int [] dp = new int [value.length] ;
        for(int i=0; i<nums.length; i++){
            value[nums[i]] += nums[i] ;
        }
        dp[0] = value[0] ;
        dp[1] = Math.max(value[0],value[1]) ;
        for(int i=2; i<value.length; i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+value[i]) ;
        }
        return dp[dp.length-1] ;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3-旋转数字
题目链接：题目链接戳这里！！！

思路1：判断是否是好数，是的话，则加1
满足下面两条则是好数：
1-不含有3，4，7其中一个
2-含有2，5，6，9其中一个

class Solution {
    public int rotatedDigits(int n) {
        int cnt = 0 ;
        for(int i=1; i<=n; i++){
            if(goodNumder(i)){
                cnt ++ ;
            }
        }
        return cnt ;
    }
    public boolean goodNumder(int n){
        String str = String.valueOf(n) ;
        boolean flag = false ;
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i)=='3' || str.charAt(i)=='4' || str.charAt(i)=='7'){
                return false ;
            }else if(str.charAt(i)=='2' || str.charAt(i)=='5' || str.charAt(i)=='6' || str.charAt(i)=='9'){
                flag = true ;
            }
        }
        return flag ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4-最长的斐波那契子序列长度
题目链接：题目链接戳这里！！！

思路：dp[i][j]表示从i到j位置的最长斐波那契序列，用map存储对应的元素和下标，如果每组(3个数字)斐波那契的第一个数字出现，则更新dp数组。

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length ;
        if(n<3){
            return 0 ;
        }
        Map<Integer,Integer> map = new HashMap<>() ;
        for(int i=0; i<n; i++){
            map.put(arr[i],i) ;
        }
        int [][] dp = new int [n][n] ;
       int res = 0 ;
       for(int i=0; i<n;i++){
           for(int j=0; j<i; j++){
               if(map.containsKey(arr[i]-arr[j]) && arr[i]-arr[j]<arr[j]){
                   int k = map.get(arr[i]-arr[j]) ;
                   dp[j][i] = Math.max(dp[k][j]+1,dp[j][i]) ;
                   dp[j][i] = Math.max(dp[j][i],3) ;
               }
               res = Math.max(res, dp[j][i]) ;
           }
       }
       return res ;


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

5-买卖股票的最佳时机含手续费
题目链接：题目链接戳这里！！！

思路：第i天就两种状态，持有股票或者不持有股票
若持有股票，则又分为两种情况：1-前一天就持有，2-今天买入
若不持有股票，也分为两种情况：1-前一天不持有，2-今天卖出
我们最后找到最后依次不持有，就是我们的答案了
dp[i][1]:表示第i天持有
dp[i][0]:表示第i天不持有

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int [][] dp = new int [prices.length][2] ;
        dp[0][0] = 0; 
        dp[0][1] = -prices[0] ;
        for(int i=1;i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee) ;
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]) ;
        } 
        return dp[dp.length-1][0] ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

6-下降路径最小和
题目链接：题目链接戳这里！！！

思路：自底向上，每次将下方的三个中最小的，加到上方，最后第一行中最小的就算下降路径最小和。

class Solution {
 
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length ;
       
        for(int row=n-2; row>=0; row--){
            for(int col=0; col<n; col++){
                int value = matrix[row+1][col] ;
                if(col-1>=0){
                    value = Math.min(matrix[row+1][col-1],value) ;
                }
                if(col+1<n){
                    value = Math.min(matrix[row+1][col+1],value) ;
                }
                matrix[row][col] += value ;
            }
        }
        int ans = Integer.MAX_VALUE ;
        for(int res : matrix[0]){
            ans = Math.min(ans, res) ;
        }
        return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

7-组合种数IV
题目链接：题目链接戳这里！！！

思路：dp[x]:选取的元素之和等于x的方案数。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int [] dp = new int [target+1] ;
        dp[0] = 1 ;
        for(int i=0; i<=target; i++){
            for(int num : nums){
                if(i-num>=0){
                    dp[i] += dp[i-num] ;
                }
            }
        }
        return dp[target] ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

8-买卖股票的最佳时机IV
题目链接：题目链接戳这里！！！

思路：动态规划
我们用 buy[i][j] 表示对于数组prices[0…i] 中的价格而言，进行恰好 j笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用 sale[i][j] 表示恰好进行 j 笔交易，并且当前手上不持有股票，这种情况下的最大利润。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length ;
        if(n==0){
            return 0;
        }
        int [][] buy = new int [n][k+1] ;
        int [][] sale = new int [n][k+1] ;
        buy[0][0] = -prices[0] ;

           for (int i = 1; i <= k; ++i) {
            buy[0][i] = sale[0][i] = Integer.MIN_VALUE / 2;
        }


        for(int i=1; i<n; i++){
            buy[i][0] = Math.max(buy[i-1][0],sale[i-1][0]-prices[i]) ;
            for(int j=1; j<=k; j++){
            buy[i][j] = Math.max(buy[i-1][j],sale[i-1][j]-prices[i]) ;
            sale[i][j] = Math.max(sale[i-1][j],buy[i-1][j-1]+prices[i]) ;
            }
        }
        int max = Integer.MIN_VALUE ;
        for(int sell : sale[n-1]){
            max = Math.max(sell,max) ;
        }
        return max ;
        }
    
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

9-01矩阵
题目链接：题目链接戳这里！！！

思路：从左上角和右下角进行递推。
递推表达式如下：

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length ;
        int n = mat[0].length ;

        int [][] dp = new int [m][n] ;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                dp[i][j] = (mat[i][j] == 0 ? 0 : Integer.MAX_VALUE/2);
            }
        }
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i-1>=0){
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1) ;
                }
                if(j-1>=0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1) ;
                }
            }
        }
        for(int i=m-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                if(i+1<m){
                    dp[i][j] = Math.min(dp[i][j],dp[i+1][j]+1) ;
                }
                if(j+1<n){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j+1]+1) ;
                }
            }
        }
        return dp ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

10-除数博弈
题目链接：题目链接戳这里！！！

思路：我们定义 dp[i] 表示当前数字 i 的时候先手是处于必胜态还是必败态，}true 表示先手必胜，alse 表示先手必败，从前往后递推，如果取一个数字后的状态为必败态，那么当前的状态必然是必胜态。

class Solution {
    public boolean divisorGame(int n) {
        if(n==1){
            return false ;
        }
        if(n==2){
            return true ;
        }
        boolean [] dp = new boolean[n+1] ;
        dp[1]=false ;
        dp[2]=true ;
        for(int i=3; i<=n; i++){
            for(int j=1; j<i; j++){
                if((i%j)==0 && !dp[i-j]){
                    dp[i] = true ;
                    break ;
                }
            }
        }
        return dp[n] ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

不积硅步，无以至千里，不积小流，无以成江河。