您现在的位置是：首页 >技术教程 >代码随想录第53天网站首页技术教程

1.最长公共子序列：

红字的问题都是和最长重复子数组那题的代码进行比较的出来的

动规五部曲分析如下：

1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

1.为什么这里的dp[i][j]不是以下标i - 1为结尾的text1，和以下标j - 1为结尾的text2，最长公共子序列长度呢？

因为最长重复子数组是要求连续的，你递推的时候dp[i-1][j-1]的值一定是和以i-2和j-2为结尾连起来最大长度，然后如果A[i]==B[j],那么再加1，连续的长度有增加了；但是这道题是不用连续的，前面的所有元素都可以作为结尾：

最长重复子数组：

以下标i - 1为结尾的A，以下标j - 1为结尾的B，连续的，如果i=j那就+1

以下标i - 1为结尾的A，以下标j - 1为结尾的B，不连续的，就算i=j也不行因为中间断掉了。

最长公共子序列：

2.为什么最长递增子序列也是不连续的但是定义dp[i]也是以i-1结尾？

因为他要找严格递增子序列，所以必须确定序列最后一个元素的值，才能比较新加入序列的元素是不是递增的。本题求的是不必连续的相等子序列，就不需要知道序列最后一个元素的值，只要知道范围内相等的序列长度就行，新来的相等元素可以直接加在序列后面

有同学会问：为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？

这样定义是为了后面代码实现方便，如果非要定义为长度为[0, i]的字符串text1也可以，我在 动态规划：718. 最长重复子数组 (opens new window)中的「拓展」里 详细讲解了区别所在，其实就是简化了dp数组第一行和第一列的初始化逻辑。

     2.确定递推公式

主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

3.这里为什么不相等会有操作，为什么操作是dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])？

首先要明白一点，最长重复子数组是连续的，比如{3，2，1}和{3，1，2}是1，而最长公共子序列是不连续的{a，c，b}和{a，b，c}是2，所以他的递推公式不能和最长重复子数组一样，因为在最长重复子数组中如果要判断的两个元素是不同的，那么这个结果就不能继续加上去了，就断掉了（当然会有result取遍历过程中的最大值），所以他不同时没有操作，但是在最长公共子序列中他不用断，他一直是最大值，所以在遍历到最后就是答案，因为要最大值并且可以断的前提下，所以在不相等时要分别判断舍弃正在遍历的一个元素，取其中的最大值，比如：{a,c,b}和{a,b,d},因为最后一个元素b！=d，所以max（2，1），取最大值就是max，断的话就是分别舍弃正在遍历的一个元素

 

4.为什么不相等的时候max里面没有dp[i-1][j-1]？

因为dp[i-1][j]和dp[i][j-1]已经包括了dp[i-1][j-1],比如dp[i-1]是2个元素，dp[j-1]是2个元素，dp[i]是3个元素，dp[j]是3个元素：

 

因为有max，而且第一种肯定比第2，3种小，所以没有dp[i-1][j-1]

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

代码如下：

if (text1[i - 1] == text2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}

      3.dp数组如何初始化

先看看dp[i][0]应该是多少呢？

test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;

同理dp[0][j]也是0。

其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。

代码：

vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

    4.确定遍历顺序

从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图：

那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。

     5.举例推导dp数组

以输入：text1 = "abcde", text2 = "ace" 为例，dp状态如图：

最后红框dp[text1.size()][text2.size()]为最终结果

5.为什么这里dp[text1.size()][text2.size()]为最终结果而不是取遍历中的最大值？

当char1不等于char2的时候，已经取了max（dp【i-1】【j】, dp【i】【j-1】），是实时更新到最大结果的，因为题目不要求是连续的，所以不管char1等不等于char2，每次dp【i】【j】的结果都是实时更新到最大的结果。第718题，跟这个很类似，但是因为题目要求是连续的，所以在遇到num1不等于num2的时候，不能把之前的结果用来更新

以上分析完毕，C++代码如下：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

2.不相交的线：

绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

拿示例一A = [1,4,2], B = [1,2,4]为例，相交情况如图：

其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）

这么分析完之后，大家可以发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

这道题求最大连线数为什么就变成了求两个数组的最长公共子序列的长度？

首先明白定义（这里用字符串解释，和数组一样的）：

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

然后连线的要求是相同且不能相交，相同就是两个数组共同拥有的，就是公共；不能相交就是这个公共子序列的各个元素在A数组中的相对方向怎么样，在B中也这么样，比如上面的A中1必须在4的左边，那B中1也得在4的左边，不管你怎么变。

代码和上面那道题一模一样:

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[A.size()][B.size()];
    }
};

3.最大子数组和：

动规五部曲如下：

1. 确定dp数组（dp table）以及下标的含义

dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。

    2.确定递推公式

dp[i]只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

    3.dp数组如何初始化

从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。

dp[0]应该是多少呢?

根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。

    4.确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

   5.举例推导dp数组

以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下： 

注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。

在回顾一下dp[i]的定义：包括下标i  之前的最大连续子序列和为dp[i]。

那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。

所以在递推公式的时候，可以直接选出最大的dp[i]。

以上动规五部曲分析完毕，完整代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
        }
        return result;
    }
};