Classic problem of leetcode dynamic programming (I)

62. Different paths

https://leetcode.cn/problems/unique-paths/

Ideas ： For each location (i,j), It can come from two places , One is above , One is on the left , therefore (i,j) The path to the location is $dp[i][j]=dp[i-1][j]+dp[i][j-1]$, The boundary conditions include the first row and the first column , The first row and the first column have only one path to , Initialize to 1

class Solution {
    
    public int uniquePaths(int m, int n) {
    
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
    // The first column has only 1 Three paths to 
            dp[i][0]=1;
        }
        for(int j=0;j<n;j++){
    // The first line is just 1 Three paths to 
            dp[0][j]=1;
        }
        for(int i=1;i<m;i++){
    
            for(int j=1;j<n;j++){
    
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
//O(mn)
//O(mn)

63. Different paths II

https://leetcode.cn/problems/unique-paths-ii/

Ideas ： Same as different path I This question , The recurrence formula here satisfies the condition only when there is no obstacle in the current position , In addition, when initializing the boundary conditions , Stop initializing when encountering obstacles , Because the back is inaccessible

class Solution {
    
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
        int m=obstacleGrid.length,n=obstacleGrid[0].length;
        int[][] dp=new int[m][n];
        for(int i=0;i<m&&obstacleGrid[i][0]==0;i++){
    // Initialize the first column   If you encounter obstacles, you can't reach them from the beginning to the future 
            dp[i][0]=1;
        }
        for(int j=0;j<n&&obstacleGrid[0][j]==0;j++){
    // Initialize the first line   If you encounter obstacles, you can't reach them from the beginning to the future 
            dp[0][j]=1;
        }
        for(int i=1;i<m;i++){
    
            for(int j=1;j<n;j++){
    
                if(obstacleGrid[i][j]==0){
    // Location (i,j) There are no obstacles 
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
//O(mn)
//O(mn)

64. Minimum path sum

https://leetcode.cn/problems/minimum-path-sum/

Ideas ： and Different paths The two topics are similar , First initialize the first row and the first column , Treat as a boundary condition , Then for other locations (i,j), The equation of state transfer is : $dp[i][j]=min(dp[i-1][j],dp[i][j-1]+grid[i][j]$, Finally back to dp[m-1][n-1]

class Solution {
    
    public int minPathSum(int[][] grid) {
    
        int m=grid.length,n=grid[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++){
    // Initialize the first column 
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        for(int j=1;j<n;j++){
    // Initialize the first line 
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }
        for(int i=1;i<m;i++){
    
            for(int j=1;j<n;j++){
    
                // The shorter path in the upper right and left grids of the current position moves from 
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
//O(mn)
//O(mn)

5. Longest text substring

https://leetcode.cn/problems/longest-palindromic-substring/

Ideas ： For a substring s[i:j] , When s[i:j] Is a palindrome string , Yes s[i+1:j-1] Is a palindrome string and s[i]=s[j]

$$dp[i][j]=\{\begin{array}{ll}true,& \text{if i=j}\\ s[i]=s[j]\&\&dp[i+1][j-1],& \end{array}$$

class Solution {
    
    public String longestPalindrome(String s) {
    
        int n=s.length();
        if(n<2){
    
            return s;
        }
        int start=0;
        int maxLen=1;
        boolean[][] dp=new boolean[n][n];
        for(int i=0;i<n;i++){
    
            dp[i][i]=true;// A single character is a palindrome string 
        }
        for(int len=2;len<=n;len++){
    
            for(int i=0;i<n;i++){
    //i It's the starting position 
                int j=i+len-1;//j It's the end position 
                if(j>=n){
    // Transboundary 
                    break;
                }
                if(s.charAt(i)!=s.charAt(j)){
    //s[i]!=s[j]
                    dp[i][j]=false;
                }else{
    //s[i]=s[j]
                    if(j-i<3){
    // The length is 2&s[i]=s[j]  It is a palindrome string directly 
                        dp[i][j]=true;
                    }else{
    
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&&j-i+1>maxLen){
    //s[i:j] Is a palindrome string and the string is longer 
                    maxLen=j-i+1;
                    start=i;
                }
            }
           
        }
        return s.substring(start,start+maxLen);
    }
    
}
//O(n^2)
//O(n^2)

The finger of the sword Offer II 091. Paint the house

https://leetcode.cn/problems/JEj789/

Ideas ： Dynamic programming ,dp[i][j] The house was painted 0 Number to i No. and i The color of House No j(0: Red 1： Blue 2： green )
Then the state transfer equation is ：

$$\begin{gathered} dp[i][0]=min(dp[i-1][1],dp[i-1][2])+cost[i][0] \\ dp[i][1]=min(dp[i-1][0],dp[i-1][2])+cost[i][1] \\ dp[i][2]=min(dp[i-1][0],dp[i-1][1])+cost[i][2] \end{gathered}$$

Dangran 0 House No ,dp[0][0]=cost[0][0],dp[0][1]=cost[0][1],dp[0][2]=cost[0][2], To save space , You can directly use the existing costs Array as dp Array

class Solution {
    
    public int minCost(int[][] costs) {
    
        int n=costs.length;
        for(int i=1;i<n;i++){
    
            costs[i][0]=Math.min(costs[i-1][1],costs[i-1][2])+costs[i][0];
            costs[i][1]=Math.min(costs[i-1][0],costs[i-1][2])+costs[i][1];
            costs[i][2]=Math.min(costs[i-1][0],costs[i-1][1])+costs[i][2];
        }
        return Math.min(costs[n-1][0],Math.min(costs[n-1][1],costs[n-1][2]));
    }
}
//O(n)
//O(1)

53. Maximum subarray and

https://leetcode.cn/problems/maximum-subarray/

Ideas ：dp[i] Represents an array element nums[i] The largest contiguous subarray at the end and
$dp[i]=max(dp[i-1]+nums[i],nums[i])$, If you add dp[i-1] The continuity and the greater are added , Otherwise, we should nums[i] The greatest continuous sum at the end is nums[i], Then find out all dp[i] The largest of , The largest continuous subarray of a bitwise whole and

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int n=nums.length;
        int[]dp=new int[n];
        int maxSum=nums[0];
        dp[0]=nums[0];
        for(int i=1;i<n;i++){
    
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            maxSum=Math.max(maxSum,dp[i]);

        }
        return maxSum;
    }
}
//O(n)
//O(n)

121. The best time to buy and sell stocks

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

Ideas ： The equation of state transfer is $dp[i]=max(dp[i-1],prices[i]-minPrice)$, dp[i] Express [0-i] The maximum profit you can make in a day , The biggest profit is in the front i-1 Day's maximum profit and day i Take the maximum profit from the day sale

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int n=prices.length;
        int minPrice=prices[0];
        int[] dp=new int[prices.length];
        dp[0]=0;// The first 0 Days without profit 
        for(int i=1;i<n;i++){
    
            minPrice=Math.min(minPrice,prices[i]);// to update [0:i] The minimum price in the interval 
            dp[i]=Math.max(dp[i-1],prices[i]-minPrice);// The first i Day sell   Buy on the day of minimum price （ Hypothesis number 1 j The lowest price per day  j Belong to [0:i-1]）
               // Update maximum profit 
            
        }
        return dp[n-1];
    }
}
//O(n)
//O(n)

Because only the value of the previous state will be used each time , Can be dp The array is reduced to a variable maxProfit, Reduce space overhead

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int minPrice=prices[0];
        int maxProfit=0;
        for(int i=1;i<prices.length;i++){
    
            minPrice=Math.min(minPrice,prices[i]);// to update [0:i] The minimum price in the interval 
            maxProfit=Math.max(maxProfit,prices[i]-minPrice);// The first i Day sell   Buy on the day of minimum price （ Hypothesis number 1 j The lowest price per day  j Belong to [0:i-1]）
               ;// Update maximum profit 
            
        }
        return maxProfit;
    }
}

122. The best time to buy and sell stocks II

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

Ideas ： There may be no stock in hand one day , You may have a stock in your hand , Write it down as dp[i][0] For in the i The maximum profit that can be made when there is no stock in heaven's hands ,dp[i][1] For in the i God has 1 The maximum profit you can make when you buy shares

dp[i][0] Two states can be transferred from ：

1. The first i-1 God has no stock in his hand
2. The first i-1 God has stock in his hand , But the first i God sold it

so dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]

dp[i][1] Two states can be transferred from ：

1. The first i-1 God has stock in his hand
2. The first i-1 God has no stock in his hand , But the first i Day bought a stock

so dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int n=prices.length;
        int[][] dp=new int[n][2];
        dp[0][0]=0;// The first 0 The profit without stock in Tian's hand is 0
        dp[0][1]=-prices[0];// The first 0 Sky buying   So the profit is negative 
        for(int i=1;i<n;i++){
    
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
}
//O(n)
//O(n)

In the state transition equation above , The state of each day is only related to the state of the previous day , It has nothing to do with earlier states , So you can put dp A two-dimensional array is represented by two variables , Reduce space overhead

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int n=prices.length;
        int dp0=0;// The first 0 The profit without stock in Tian's hand is 0
        int dp1=-prices[0];// The first 0 Sky buying   So the profit is negative 
        for(int i=1;i<n;i++){
    
            dp0=Math.max(dp0,dp1+prices[i]);
            dp1=Math.max(dp1,dp0-prices[i]);
        }
        return Math.max(dp0,dp1);
    }
}
//O(n)
//O(1)

123. The best time to buy and sell stocks III

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

Ideas ： At the end of any day , We will be in the following 5 One of the States

1. No action has been taken
2. Only one purchase operation has been carried out
3. Have conducted a buy operation and a sell operation , That is to complete a transaction
4. After a transaction is completed, another purchase operation is carried out
5. Completed two transactions

state 1 There was no operation , So the profit is 0, This state does not consider , The maximum profits of the other four states are recorded as buy1 sell1 buy2 sell2

$$\{\begin{array}{l}buy1=max(buy1,-prices[i])\\ sell1=max(sell1,buy1+prices[i]\\ buy2=max(buy2,sell1-prices[i])\\ sell2=max(sell2,buy2+prices[i])\end{array}$$

The boundary conditions ： For the first 0 God ,buy1=-prices[i], sell1 It means buying and selling on the same day , therefore sell1=0, buy2 It means to buy again after completing a transaction on the same day , therefore buy2=-prices[i], sell2=0

Return value ： The maximum profit must depend on the profit after the sale , Suppose that the profit from completing a transaction is the largest , Then you can make another transaction on the same day , such sell1 The state of can be transferred to sell2 The state of , So finally back sell2

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int buy1=-prices[0],sell1=0;
        int buy2=-prices[0],sell2=0;
        for(int i=1;i<prices.length;i++){
    
            buy1=Math.max(buy1,-prices[i]);//( No operation , Buy on the same day )
            sell1=Math.max(sell1,buy1+prices[i]);//( No operation , Sell after last buy )
            buy2=Math.max(buy2,sell1-prices[i]);//( No operation , Buy after the last sale )
            sell2=Math.max(sell2,buy2+prices[i]);//( No operation , Sell after last buy )
        }
        return sell2;
    }
}
//O(n)
//O(1)

188. The best time to buy and sell stocks IV

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

Ideas ： The first step is to consider n/2 and k The size of the relationship , If k>=n/2, Equivalent to an unlimited number of transactions , This translates to 122. The best time to buy and sell stocks II, We can use greedy algorithm to solve this problem ; When k<n/2 when , Use dynamic programming

Definition buy[i][j] It means the first one i The day goes on j Transactions （ The first j Buy stocks for the first time ） Maximum profit at
Definition sell[i][j] It means the first one i The day goes on j Transactions （ The first j Sell stocks for the first time ） Maximum profit at

$buy[i][j]=max(buy[i-1][j],sell[i-1][j-1]-prices[i])$: max（ The first i Days without trading , In the i-1 Tiandi j-1 Buy a stock on the basis of this transaction ）

$sell[i][j]=max(sell[i-1][j],buy[i][j]+prices[i])$: max（ The first i Days without trading , In the i Tiandi j Buy a stock on the basis of this transaction ）

class Solution {
    
    public int maxProfit(int k, int[] prices) {
    
        if (prices.length == 0) {
    
            return 0;
        }

        int n = prices.length;
        if(k>=n/2){
    
            return greedy(prices);
        }
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];

        buy[0][0] = 0;
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
    
            buy[0][i] = -prices[0];
            sell[0][i]=0;
        }

        for (int i = 1; i < n; ++i) {
    
            for (int j = 1; j <= k; ++j) {
    
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j-1] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i][j]+prices[i]); 
                // The first i The day went on j Purchase of this transaction -> The first i The day went on j Sale of this transaction 
                // buy[i][j]+prices[i]-->sell[i][j] 
                // The first i-1 The day went on j Purchase of this transaction -> The first i The day went on j Sale of this transaction 
                //buy[i - 1][j]+prices[i]-->sell[i][j]
                // because buy[i][j]>=buy[i - 1][j]  So here we just need to write buy[i][j]+prices[i]
                
            }
        }

        return Arrays.stream(sell[n - 1]).max().getAsInt();
    }
    public int greedy(int[] prices){
    
        int ans=0;
        for(int i=1;i<prices.length;i++){
    
            if(prices[i]-prices[i-1]>0){
    
                ans+=prices[i]-prices[i-1];
            }
        }
        return ans;
    }
}
//O(nk)  go greedy The time is n  The time not to go is nk
//O(nk)  go greedy The time is 1  The time not to go is nk