一、动态规划DP 子序列问题Ⅱ

1、leetcode.cn/problems/longest-common-subsequence/description/" rel="nofollow">最长公共子序列 1143

确定dp数组含义，dp[i][j]表示长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列的长度。
dp转移关系，对于当前值dp[i][j], 分为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[i-1]或者text2[j-1]中选取最大值，$dp[i][j]=max(dp[i][j-1],dp[i-1][j])$。
边界的初始值都为0，因为还没有公共子序列。

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++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[m][n];}
};

从递推公式来看，当前的dp值dp[i][j]只与上方、左方和左上方的值有关，可以进一步优化空间复杂度。只与上方和左方有关，之前的博客介绍过优化的写法，这题多了一个左上方的值，如果只采用一维数组，那么左上方的值会被左方的值更新替代，所以需要额外的变量来存储和更新当前值的左上方值。
同时，将二维数组优化成一维数组时，还需要注意边界和初始化的问题。

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

2、leetcode.cn/problems/uncrossed-lines/description/" rel="nofollow">不相交的线 1035

这题也是有两个容器，只不过由字符串变成了整型数组。仍可套用相似的dp数组定义。
对于递推关系的推导，也可分为nums1[i-1]与nums2[j-1]相同和不相同，对于相同的情况，这两个数可以画一条线，所以$dp[i][j]=dp[i-1][j-1]+1$；对于不同的情况，这两明确不能画线，则可以从dp[i-1][j]、dp[i][j-1]取最大值，的$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$。可以发现，递推公式与上一题也一样。
初始化也是，边界都初始化为0，因为不能画出线。
代码如下，这题和上一题可以说是一模一样。

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){if(nums1[i-1]==nums2[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[m][n];}
};

空间复杂度优化也是一样的，甚至代码都一模一样，就不赘述了。

3、leetcode.cn/problems/maximum-subarray/description/" rel="nofollow">最大子数组和 53

dp数组dp[i]表示下标0~i（以nums[i]为结尾）的最大连续子序列和，递推公式为$dp[i]=max(nums[i],nums[i]+dp[i-1])$

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

发现当前值dp[i]只与dp[i-1]有关，所以可以只采用变量来替代数组，优化空间复杂度，代码如下：

class Solution {
public:int maxSubArray(vector<int>& nums) {int ans = nums[0], cur = nums[0];for(int i=1; i<nums.size(); ++i){cur = max(nums[i], nums[i] + cur);ans = max(ans, cur);}return ans;}
};

4、leetcode.cn/problems/is-subsequence/description/" rel="nofollow">判断子序列 392

有两个字符串，想到dp数组含义dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度。
递推公式，对于当前dp[i][j]，分为s[i-1]与t[j-1]相等和不相等两种情况。当s[i-1]==t[j-1]，则$dp[i][j]=dp[i-1][j-1]$；当s[i-1]!=t[j-1]时，需要将这个不等的元素删掉，$dp[i][j]=dp[i][j-1]$

class Solution {
public:bool isSubsequence(string s, string t) {int m = s.size(), n = t.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for(int i=0; i<=n; ++i)dp[0][i] = 1;for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){if(s[i-1] == t[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = dp[i][j-1];}}}return dp[m][n];}
};

class Solution {
public:bool isSubsequence(string s, string t) {int m = s.size(), n = t.size();vector<int> dp(n+1, 1);for(int i=1; i<=m; ++i){int leftup = dp[0];dp[0] = 0;for(int j=1; j<=n; ++j){int tmp = dp[j];if(s[i-1] == t[j-1]){dp[j] = leftup;}else{dp[j] = dp[j-1];}leftup = tmp;}}return dp[n];}
};

也可以采用双指针的方法，使用两个指针指向两个字符串，子序列的指针碰到相等的值才移动，空间复杂度更低。

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.size();int j = 0; // 指向s的指针for(int i=0; i<t.size(); ++i){if(t[i] == s[j])++j;if(j==n)return true;}return n==0;}
};

二、写在后面

子序列问题的递推关系比较好推导，当涉及到两个数组或者字符串时，通常要采用二维dp数组，同时也要考虑如何优化空间复杂度，看能否将二维数组优化成一维数组，这个问题的关键是理清递推公式当前值与其它值的位置关系，是否是固定的位置关系，然后需要注意边界值的初始化这些细节。