最长公共子序列算法解释

Question

因此，最长公共子序列问题的psuedocode如下所示。

最长-公共子序列(s1，s2)： 如果字符串以相同的字母c开头，则返回的结果是c加上s1和s2其余部分之间最长的公共子序列(即s1和s2没有第一个字母)。例如，“空心”和“你好”之间最长的子序列是"h“加上"ollow”和"ello“之间的最长子序列。 否则，如果字符串不以相同的字母开头，则返回以下两个字符串中的较长的两个: s1和s2的其余部分之间最长的公共子序列(s2没有第一个字母)，s1其余部分(没有第一个字母的s1)和s2之间最长的公共子序列。例如，最长-公共-子序列(“ollow”，"ello")是最长-公共-子序列(“ollow”，"llo")和最长-公共子序列(“llow”，"ello")的长度。

我不明白的部分是，当字符串不是以同一个字母开头时，为什么我们要使用(s1，没有第一个字母，s2)，(s1，s2，没有第一个字母)。当这些步骤不匹配时，我们为什么要递归地进行这些步骤？这仅仅是一种难以理解的集合算法吗？这背后的原因是什么？

Answer 1

虽然@yash已经涵盖了一切，但我将提供另一种思考方法。

通过两个字符串，假设您位于字符串A(长度m)上的位置i和字符串B(长度n)上的位置j。

如果两个字符串的当前两个字符是相同的：：

至今为止，最长公共子序列=子字符串A0.I-1和子字符串B0.j-1+ 1之间的最长公共子序列。

2.如果两个字符不同：

最长公共子序列=最大值(子字符串A0.I-1和字符串B之间最长的公共子序列，字符串A和子字符串B0.j-1之间最长的公共子序列)

如果你读了密码，你会有一个更清晰的概念。

public class Solution {

    public int longestCommonSubsequence(String A, String B) {
        if(A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }

        int m = A.length();
        int n = B.length();
        int[][] commonSubsequenceLength = new int[m + 1][n + 1];

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(A.charAt(i - 1) == B.charAt(j - 1)) {
                    commonSubsequenceLength[i][j] = commonSubsequenceLength[i - 1][j - 1] + 1;
                } else {
                    commonSubsequenceLength[i][j] = Math.max(commonSubsequenceLength[i][j - 1], commonSubsequenceLength[i - 1][j]);
                }
            }
        }

        return commonSubsequenceLength[m][n];

    }
}

Answer 2

当我们知道两个字符串的第一个字符不匹配时，很明显，我们不能像在第一种情况下那样，将字符包含在最长的子序列中。因此，我们剩下的明显选择是忽略这两个字符，并为我们的子序列搜索两个字符串的其余部分。但是如果你考虑这个例子："hello“和"ello”，你可以清楚地看到，如果我们忽略了第一个字符，我们基本上忽略了我们子序列中的第一个字符("Ello")。因此，我们有两种情况:1.删除第一个字符串的第一个字符，然后在第二个字符串中进行搜索。2.删除第二个字符串的第一个字符，并在第一个字符串中搜索。

然后我们取这两个中的最大值。

Answer 3

回答你的问题：

我不明白的部分是，当字符串不是以同一个字母开头时，为什么我们要使用(s1，没有第一个字母，s2)，(s1，s2，没有第一个字母)。当这些步骤不匹配时，我们为什么要递归地进行这些步骤？这仅仅是一种难以理解的集合算法吗？这背后的原因是什么？

我想，让您感到困惑的是递归调用。整个想法是将问题简化为一个更小的输入集。在这种情况下，每次减少一个字符。所选字符有2箱(第1或最后一次)

1. 有一个匹配(例如，“空心”中的"h“，"hello")，只需将两个字符串中的输入字符减少一个字符，并递归地调用相同的函数。
2. 没有匹配。这里有两个选项--你可以考虑第一个字符串有多余的字符，或者第二个字符串。因此，对这两种情况进行递归调用，并选择它们的最大值。

附加细节：这个问题具有典型的动态规划(DP)问题的性质。

1)最优子结构

2)重叠子问题

希望能帮上忙！