最长子序列子数组

Posted on Edited on Symbols count in article: 1.8k Reading time ≈ 2 mins.

1143 最长公共子序列

  • 子序列是可以不连续的
  • dp[i][j]的含义是text1[:i]和text2[:j]最长公共子序列，这个最长公共子序列不一定包含text1[i]和text2[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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, 0)); // 多一行一列
        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];
    }
};

718 最长重复子数组

  • 子数组是连续的
  • dp[i][j]的含义是以nums1[i]结尾的nums1[:i]和以nums2[j]结尾的nums2[:j]的最长重复子数组 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        int findLength(vector<int>& nums1, vector<int>& nums2) {
            int m = nums1.size(), n = nums2.size();
            vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
            int ret = 0;
            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;
                        ret = max(ret, dp[i][j]);
                    }
                }
            }
            return ret;
        }
    };

错误1

如果里面写成这样： 

1
2
3
4
if(nums1[i-1] == nums2[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];
则是处理非连续的“数组子序列”，对于[0,1,1,1,1]和[1,0,1,0,1]给出的答案是3，但是正确答案应该是2 
1
2
3
4
5
6
7
8
9
// 错误DP图
X | X   1   0   1   0   1
——————————————————————————
X | 0   0   0   0   0   0
0 | 0   0   1   *1  1   *1
1 | 0   1   *1  2   *2  2
1 | 0   1   *1  *2  *2  *3
1 | 0   1   *1  *2  *2  *3
1 | 0   1   *1  *2  *2  *3
1
2
3
4
5
6
7
8
9
// 正确DP图
X | X   1   0   1   0   1
——————————————————————————
X | 0   0   0   0   0   0
0 | 0   0   1   0   1   0
1 | 0   1   0   2   0   2
1 | 0   1   0   1   0   1
1 | 0   1   0   1   0   1
1 | 0   1   0   1   0   1

错误2

如果里面写成这样： 

1
2
3
4
dp[i][j] == max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]+1);
ret = max(ret, dp[i][j]);
...
return ret;
则属于彻底混淆了自己对于dp数组的定义，一定要是以nums1[i]结尾的子数组和以nums1[j]结尾的子数组的最长子数组，对于[1,0,0,0,1]和[1,0,0,1,1]给出的答案是4，但是正确答案应该是3 
1
2
3
4
5
6
7
8
9
// 错误DP图
X | X   1   0   0   0   1
——————————————————————————
X | 0   0   0   0   0   0
1 | 0   1   0   0   0   1
0 | 0   0   2   *2  *2  0
0 | 0   0   *2  3   *3  0
1 | 0   1   0   0   0   *4
1 | 0   1   0   0   0   *4
1
2
3
4
5
6
7
8
9
// 正确DP图
X | X   1   0   0   0   1
——————————————————————————
X | 0   0   0   0   0   0
1 | 0   1   0   0   0   1
0 | 0   0   2   1   1   0
0 | 0   0   1   3   2   0
1 | 0   1   0   0   0   3
1 | 0   1   0   0   0   1