Linear DP of dynamic programming

1. Concept

Dynamic programming algorithm with linear stage division is called linear dynamic programming （ Linear for short DP）. If the state contains multiple dimensions , Then each dimension is a stage of linear division , It also belongs to linear DP, As shown in the figure below ：

2. The minimum path of a triangle and

https://leetcode.cn/problems/triangle/

State transition equation ： dp[i ][j ]=max{dp[i -1][j ], dp[i -1][j -1]}+a [i ][j ]

The boundary conditions ：

The leftmost part and the rightmost boundary will only move from a position on the previous line , Only 1 Two transfer methods , Therefore, the path that goes all the way down the left and all the way down the right is the sum of array elements , Deal with these two boundaries first

class Solution {
    
    public int minimumTotal(List<List<Integer>> triangle) {
    
        int n=triangle.size();
        int[][] dp=new int[n][n];
        dp[0][0]=triangle.get(0).get(0);
        for(int i=1;i<n;i++){
    
            dp[i][0]=dp[i-1][0]+triangle.get(i).get(0);// Initialize left boundary - First column 
            dp[i][i]=dp[i-1][i-1]+triangle.get(i).get(i);// Initialize the right boundary - The last column 
        }
       
        for(int i=1;i<n;i++){
    
            for(int j=1;j<i;j++){
    
                dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i).get(j);
            }
        }
        int ans=Integer.MAX_VALUE;
        for(int j=0;j<n;j++){
    // Traverse last 1 That's ok   Find the maximum 
            ans=Math.min(ans,dp[n-1][j]);
        }
        return ans;
    }
}c	
//O(n^2)
//O(n^2)

Space optimization ：

According to the state transfer equation dp[i ][j ]=max{dp[i -1][j ], dp[i -1][j -1]}+a [i ][j ], When finding the optimal solution of the current position , just dp[i -1][j ]（ Same column as previous row ） and dp[i -1][j -1]（ The previous row is preceded by the previous column ）, So optimize the state into a one-dimensional array , Push backward from back to front

State means ： dp[j ] It means walking from the upper left corner to the j The maximum sum of the numbers passed in the column

State transition equation ： dp[j ]=max{dp[j ], dp[j -1]}+a [i ][j ]

The reason why we need to go backwards ：

According to the state transition equation ,dp[j] Depends on the previous line dp[j] and dp[j-1], If we deal with it from the front to the back , It can lead to dp[j-1] Updated ahead of time , In this way, the current line depends on dp[j-1] Not from the previous line , It's an update from the bank

class Solution {
    
    public int minimumTotal(List<List<Integer>> triangle) {
    
        int n=triangle.size();
        int[] dp=new int[n];
        dp[0]=triangle.get(0).get(0);
        for(int i=1;i<n;i++){
    
            dp[i]=dp[i-1]+triangle.get(i).get(i);
            for(int j=i-1;j>0;j--){
    
                dp[j]=Math.min(dp[j-1],dp[j])+triangle.get(i).get(j);
            }
            dp[0]=dp[0]+triangle.get(i).get(0);
        }
        int ans=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
    
            ans=Math.min(ans,dp[i]);
        }
        return ans;
    }
}

3. The longest increasing subsequence

https://leetcode.cn/problems/longest-increasing-subsequence/

Ideas ：

Create a dp Array

State means ： dp[i ] Said to a [i ] Length of the longest ascending subsequence at the end

State shift ： about 0<=j<i , if a [j ]<a [i ], Then you can put a [i ] Put it in a [j ] After the longest ascending sequence at the end , The resulting length is dp[j ]+1

State transition equation ： dp[i ]=max(dp[i ], dp[j ]+1)

class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
        int n=nums.length;
        int[] dp=new int[n];
        int ans=0;
        for(int i=0;i<n;i++){
    
            dp[i]=1;// A single character is... In length 1 Strictly increasing subsequence of 
            for(int j=0;j<i;j++){
    
               if(nums[i]>nums[j]){
    
                    dp[i]=Math.max(dp[i],dp[j]+1);
               }
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}
//O(n^2)
//O(n)

Algorithm optimization ：

class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
        int n=nums.length;
        //tails[k] The value of represents   The length is k+1 The value of the element at the end of the subsequence of 
        // In traversal calculation, each tails[k], The length of continuous update is  [1,k] The value of the element at the end of the subsequence of , Always keep the value of each tail element to a minimum  （ for example  [1,5,3],  Traverse to element 5  when , The length is  2 The value of the element at the end of the subsequence of is  5; When traversing to the element  3 when , The tail element value should be updated to  3, because  3  There is a greater chance of encountering a larger number 


        int[] tail=new int[n];
        int maxLen=1;
        tail[0]=nums[0];
        for(int i=1;i<n;i++){
    
            int num=nums[i];
            int left=0,right=maxLen-1;
            boolean flag=true;
            while(left<=right){
    
                int mid=left+(right-left)/2;
                if(num>tail[mid]){
    
                    left=mid+1;
                }else if(num<tail[mid]){
    
                    flag=false;
                    right=mid-1;
                }else if(num==tail[mid]){
    
                    flag=false;
                    right=mid-1;
                }
            }
            //left Say less than num Number of elements of 
            tail[left]=num;// The length is left The incremental subsequence of is updated with num ending 
            //flag by true explain nums[i] Greater than interval [0:maxLen-1] be-all tail[i]
            // Now you can put nums[i] Connect to tail[maxLen-1] Back   Ascending subsequence length +1
            //flag by false Will nums[i] Insert into tail The right place in j  bring tail[0...j-1]<nums[i]<=tail[j+1...]
            // therefore tail Arrays are monotonous 
            if(flag){
    
                maxLen++;
            }
        }
        return maxLen;
    }
}
//O(nlogn)
//O(n)

4. Longest common subsequence

https://leetcode.cn/problems/longest-common-subsequence/

Ideas ：

State means ： dp[i ][j ] Express x [0..i-1 ] and y [0..j-1 ] The longest common subsequence length of

State shift ： For characters in two sequences xi and yj , It can be divided into the following two cases :

• xi =yj ： solve Xi -1 and Yj -1 The length of the longest common subsequence of plus 1,dp[i ][j ]=dp[i -1][j -1]+1
  
• xi ≠yj ： You can put xi Get rid of , solve Xi -1 and Yj The longest common subsequence length of , Or the yj Get rid of , solve Xi and Yj -1 The longest common subsequence length of , Take the maximum of the two ,dp[i ][j ]=max(dp[i ][j -1], dp[i -1][j ])
  
  The boundary conditions ： dp[i ][0]=0,dp[0][j ]=0

Solve the goal ： dp[n -1][m-1 ],n 、m Is the length of two strings

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
    
        int m=text1.length(),n=text2.length();
        int[][] dp=new int[m+1][n+1];
        //dp[i][j] Express text1[0:i-1] text1[0:j-1]  Of LCS length 
        // When i=0 when  dp[0][j]=0  Said when text1 When the string is empty  LCS The length is 0
        // When j=0 when  dp[i][0]=0  Said when text2 When the string is empty  LCS The length is 0
        for(int i=1;i<=m;i++){
    
            for(int j=1;j<=n;j++){
    
                if(text1.charAt(i-1)==text2.charAt(j-1)){
    
                    dp[i][j]=dp[i-1][j-1]+1;
                }else if(dp[i-1][j]>dp[i][j-1]){
    
                    dp[i][j]=dp[i-1][j];
                }else{
    
                     dp[i][j]=dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
//O(mn)
//O(mn)

5. The maximum sum of successive subarrays

https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

State means ： dp[i ] Said to a [i ] The maximum sum at the end . Be careful ： This biggest sum is not [0…i ] The largest continuous subsets of an interval and , If we solve [0…n-1 ] The largest continuous subsets of an interval and , It needs to be from all dp[] Find the maximum in . for example {-2, 1, 2, 3,-2},dp[0]=-2,dp[1]=1,dp[2]=2,dp[3]=6,dp[4]=4, The maximum sum of continuous sub segments is 6

State shift ： if dp[i -1] Greater than or equal to 0, be dp[i -1] Add up a [i ] that will do ; otherwise dp[i ]=a [i ]; This is because dp[i -1] When it's negative , It is meaningless to solve the sum of the largest continuous subsegments

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