● 1143.最长公共子序列

1.dp数组含义。

dp[i][j]：数组1[0,i-1]范围的子数组和数组2[0,j-1]的子数组的公共子序列最长长度。注意这里不需要一定以A[i-1]/B[j-1]结尾，原因在下面有说明。

动态规划求子序列的问题，一般都是dp的下标相对于数组的下标偏移1，dp[i][j]对应A[i-1]和B[j-1]。

2.递推公式。

既然是公共子序列，如果A[i-1]==B[j-1] ，和● 300.最长递增子序列 一样，dp[i][j]应该在上一个公共子序列的基础上+1，那么上一个最长的公共子序列是哪一个，如果是dp[i][j]的定义是以A[i-1]/B[j-1]为结尾的子序列，那么要求上一个最长的公共子序列，dp[][]的两个下标有可能是[0,i-1]和[0,j-1]的任何一个值，所以这时两层循环里面还要有两层循环，肯定会超时。

所以按照dp[i][j]正确的定义，如果A[i-1]==B[j-1]的话，上一个最长的公共子序列就是dp[i-1][j-1]代表的，所以dp[i][j]=dp[i-1][j-1]+1。

如果不相等的话，不能直接跳过，比如abcde，ace，到了abc、ace的时候c!=e，那么dp[3][3]按照定义应该是2，等于dp[3][2]。把abc、ace倒过来，dp[3][3]又=dp[2][3]。A[i-1]和B[j-1]不相等，但是A[i-1]可能和B[j-1]之前的相等，B[j-1]可能和A[i-1]之前的相等，所以要取这两种情况的最大值。

so：

if(text1[i-1]==text2[j-1]){     //i-1/j-1可以加入，长度加1
     dp[i][j]=dp[i-1][j-1]+1;
}
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//2种情况

3.初始化。同样是dp[i][j]代表数组1的前i个和数组2的前j个的比较情况，所以第一行第一列都初始化为0.

4.遍历顺序。同样是i、j从1开始。

5.打印。

代码：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n1=text1.size();
        int n2=text2.size();
        
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
        for(int i=1;i<=n1;++i){
            for(int j=1;j<=n2;++j){
                if(text1[i-1]==text2[j-1]){     //i-1/j-1可以加入，长度加1
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//2种情况

            }
        }
        return dp[n1][n2];
    }
};

摘自动态规划子序列问题经典题目 | LeetCode：1143.最长公共子序列_哔哩哔哩_bilibili文无cc_评论：

之前的题目，dp代表的序列都是要以[i-1]/[i]结尾求递增序列的时候，即都要确定最后一个元素是谁。

● 300.最长递增子序列 因为要求序列有序，所以必须确定序列最后一个元素的值，才能比较新加入序列的元素是不是递增的。● 674. 最长连续递增序列 和 ● 718. 最长重复子数组 求相等序列的时候，如果求连续相等子序列，则还是要确定序列最后一个元素的值；但是本题求的是不必连续的相等子序列，就不需要知道序列最后一个元素的值，只要知道范围内相等的序列长度就行，新来的相等元素可以直接加在序列后面。

● 1035.不相交的线   

上一题所要求的公共子序列，因为这个公共子序列指的是相对顺序不变，如果把这个子序列里面相等的元素A[i]和B[j]连接起来，要么是垂直，要么向一个方向偏斜，不会有相交的情况发生。所以可以绘制的最大连线数其实就是公共子序列的最大长度。

代码随想录：看到代码大家也可以发现其实就是求两个字符串的最长公共子序列，但如果没有做过1143.最长公共子序列，本题其实还有很有难度的。这是Carl为什么要先讲上题再讲本题，大家会发现一个正确的刷题顺序对算法学习是非常重要的！上题是源题，这题是应用，需要转换。

转换的能力很重要，否则看见差不多的题目还是做不出来，要学会举一反三。

● 53. 最大子序和  动态规划方法

1.dp数组含义。

dp[i]：[0,i]范围内以nums[i]为结尾的连续子数组的最大和为dp[i]。这里又需要以nums[i]为结尾，因为确定了子数组最后一个元素，才能在子数组后面接上nums[i]，也就是能根据dp[i-1]得到dp[i]。

2.递推公式。

可以根据nums[i]的正负来分情况递推吗，不行。nums[i]无论是正还是负，都需要加在dp[i]里面，所以只能看dp[i-1]是+还是-，如果是+，可以加上dp[i-1]。如果是-，i前面的子数组最大和是负数，那还不如不加dp[i-1]，连续子数组重新从i开始。

可见应该取两者的较大值，即：dp[i]=max(dp[i-1],0)+nums[i];

可见和贪心的思路是一样的，dp[i-1]就是i上一轮的sum，如果sum<0，重新从i开始统计，即sum赋值为0；如果sum>0，加上nums[i]。然后接着下一轮循环。

3.初始化。从左到右

dp[0]=max_sum=nums[0]；

4.遍历顺序。

5.打印。

贪心算法和动态规划的代码：

//贪心
// class Solution {
// public:
//     int maxSubArray(vector<int>& nums) {
//         int max_sum=INT_MIN;
//         int sum=0;
//         for(int i=0;i<nums.size();++i){
//             if(sum<0){
//                 sum=0;      //重新从下一个开始求和
//             }  
//             sum+=nums[i];
//             if(sum>max_sum)max_sum=sum;
                                             
//         }
//         return max_sum;
//     }
// };


//动态规划
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n);
        dp[0]=nums[0];
        int max_sum=dp[0];
        for(int i=1;i<n;++i){
            dp[i]=max(dp[i-1],0)+nums[i];
            max_sum=max(dp[i],max_sum);
        }
        return max_sum;
    }
};