Java描述 LeetCode，1143. Longest Common Subsequence

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力。

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-subsequence

根据之前有一道题目，Java描述 LeetCode，718. Maximum Length of Repeated Subarray。上一道是最长重复的公共子数组，那里是连续的，我们现在的这道题要求是不连续的，我们大概也能想到，dp[i][j] 代表text1[0:i]和text2[0:j]的最长公共子序列的。

（[0:i] 代表从索引0的位置开始数i个数字，有点像python切片的意思）

当位置i和位置j的字符相同的时候就可以在之前的最优解上+1，也就是状态转移方程：dp[i][j] = dp[i-1][j-1] + 1，如果不想等呢？重点是这边不想等的地方，比如text1的子序列：abcd text2的子序列：ac 我们肉眼都能看出这两个的最长子序列个数是2，此时i=4, j = 2 text1[i - 1] =d; text[j - 1]=c，d不等于c，考虑以下两种情况，取最大值。ps：这里一开始我是没有想到的，一开始我只考虑了当中的一种情况。那么不想等的状态转移方程就是：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

public static int longestCommonSubsequence(String text1, String text2) {
    int n = text1.length();
    int m = text2.length();
	
	// 1~n 1~m
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char a = text1.charAt(i - 1);
            char b = text2.charAt(j - 1);
            if (a == b) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    System.out.println(Arrays.deepToString(dp));
    return dp[n][m];
}

同样我们讲实际有效范围定到1～n 和 1～m，好处是，可以利用状态转移方程直接填值，如果，范围是0～n-1，那么就需要对第一行和第一列初始化，知道0-1背包的应该能够理解这个事情。在官网链接里面有表格，一眼就可以看出，二维数组0行和0列都是0。

我们知道有滚动数组这个东西，这边能不能用上滚动数组呢？于是我写出了下面的代码：

public static int longestCommonSubsequence2(String text1, String text2) {
    int n = text1.length();
    int m = text2.length();

    int[] dp = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char a = text1.charAt(i - 1);
            char b = text2.charAt(j - 1);
            if (a == b) {
                dp[j] = dp[j - 1] + 1;
            } else {
                dp[j] = Math.max(dp[j - 1], dp[j]);
            }
        }
        System.out.println(Arrays.toString(dp));
    }
    return dp[m];
}

但是答案是不对的，如果你知道0-1背包和完全背包，就会发现0-1他们的关系是这样的：

你不管按照0-1背包从右向左遍历还是完全背包从左向右遍历，这边都会覆盖掉自己需要的值。你可以把dp滚动数组的每一步打印出来和二维的进行比较，你就会发现这个问题了。如果硬对空间优化的话，也是有办法的，毕竟只依赖于两行，感觉用两个数组表示应该可以。

这边写的可能不是特别清楚，我的表达能力有问题QAQ，我按照我的理解应该是说清楚了。但是如果你不知道0-1背包和完全背包，你肯定不知道我在说啥，包括为啥有效范围1～n，为啥数组第0行和第0列要空着，默认是0。这样的好处在哪里等。