Summary of leetcode's dynamic programming 5

leetcode Summary of dynamic programming 5

1- The smallest of two strings ASCII Delete and
Topic link ： The title link is here ！！！

Ideas ： Dynamic programming
dp[i][j] Said to i-1 a null-terminated string s1 And with j-1 a null-terminated string s2 Keep the same deleted minimum ASCII character .

initialization dp Array
If one of them is an empty string , In order to keep them the same , You need to delete all the characters of another .

If s1.charAt(i-1)==s2.charAt(j-1), You don't need to delete , The recurrence formula is as follows ：
dp[i][j] = dp[i-1][j-1]
otherwise , You need to delete one of the two ASCII Small , Recursive down ：
dp[i][j] = Math.min(dp[i-1][j]+(s1.charAt(i-1)), dp[i][j-1]+(s2.charAt(j-1))) ;

AC The code is as follows ：

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()] ;
    }
}

2- Delete and get points
Topic link ： The title link is here ！！！

Ideas ： take nums The array becomes the sum of each number , Then it becomes the problem of house raiding , You can only choose between stealing and not stealing every time .

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] ;

    }
}

3- Rotate the numbers
Topic link ： The title link is here ！！！

Ideas 1： Judge whether it is a good number , If yes , Then add 1
Satisfying the following two is a good number ：
1- It doesn't contain 3,4,7 One of them
2- contain 2,5,6,9 One of them

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 ;
    }
}

4- The longest Fibonacci subsequence length
Topic link ： The title link is here ！！！

Ideas ：dp[i][j] From i To j The longest Fibonacci sequence of positions , use map Store the corresponding elements and subscripts , If each group (3 A digital ) The first number of Fibonacci appears , Update dp Array .

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 ;


    }
}

5- The best time to buy and sell stocks includes handling fees
Topic link ： The title link is here ！！！

Ideas ： The first i There are two states in heaven , Holding or not holding shares
If holding shares , Then it can be divided into two situations ：1- Held the day before ,2- Buy today
If you do not hold shares , There are also two situations ：1- Didn't hold... The day before ,2- Sell today
We finally found that we didn't hold it in turn , That's our answer
dp[i][1]: It means the first one i Day holding
dp[i][0]: It means the first one i Days don't hold

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] ;
    }
}

6- The descent path is the smallest and
Topic link ： The title link is here ！！！

Ideas ： Bottom up , Put the smallest of the three below each time , Add to top , Finally, the smallest in the first line is the minimum sum of the descent path .

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 ;
}
}

7- Number of combinations IV
Topic link ： The title link is here ！！！

Ideas ：dp[x]: The sum of the selected elements is equal to x Number of alternatives .

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] ;
    }
}

8- The best time to buy and sell stocks IV
Topic link ： The title link is here ！！！

Ideas ： Dynamic programming
We use it buy[i][j] For an array prices[0…i] In terms of price , Proceed exactly j transaction , And currently holds a stock , The maximum profit in this case ; use sale[i][j] It means that j transaction , And does not currently hold shares , The maximum profit in this case .

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 ;
        }
    
    }

9-01 matrix
Topic link ： The title link is here ！！！

Ideas ： Recursion from the upper left corner and the lower right corner .
The recursive expression is as follows ：

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 ;
    }
}

10- Divisor game
Topic link ： The title link is here ！！！

Ideas ： We define dp[i] Represents the current number i Whether the first hand is in the state of winning or losing ,}true The first to win ,alse It means that the first hand will lose , Recursion after going , If the state after taking a number is inevitable , Then the current state must be winning .

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] ;
    }
}

No silicon step , A thousand miles , Don't product the little stream , Nothing can be a river .