最长子序列子数组

发表于 更新于 本文字数： 665 阅读时长 ≈ 2 分钟

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