提问人：knightcool 提问时间：5/14/2020 更新时间：5/16/2020 访问量：879
最长公共子序列（LCS）直觉
Longest Common Subsequence(LCS) intuition
问：
LCS 代码的递归版本如下所示（m、n 分别是字符串 X 和 Y 的长度）
int lcs( char[] X, char[] Y, int m, int n ) {
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
我注意到这个算法从末尾删除字符串的字符，并创建原始两个字符串的各种子字符串，然后尝试寻找匹配项。
我不明白的是，由于它只考虑某些子字符串而不是所有可能的子序列，因此如何保证该算法提供正确的结果？这背后有逻辑/数学/直观的证明吗？
答：
0赞
mksteve
5/14/2020
#1
当最后一个字符相同时，它会计算 lcs（ X， Y， m-1， n-1）。
或
当字符不同时，它会同时计算 lcs（ X， Y， m-1，n ） 和 lcs（ X， Y， m， n-1）。
因此，它涵盖了所有可能的解决方案。
如果长度为 0.则 lcs 为 0。 如果最后（或第一项）相同，则 lcs 为 1 + lcs（X，Y，m-1，n-1） 该子句通过将公共元素添加到 lcs 中，并找到 2 个较短字符串中较小的 lcs 来减少问题。
最后，最长的子序列是
lcs（X， Y， m-1， n）
或
lcs（X， Y， m， n-1）
所以当要求计算lcs（ “abce”， “bghci”， 4， 5）;
if( m(4) == 0 || n(5) == 0 ) // evaluates to false
if( X[3]('e') == Y[4] ) // evaluates to false
return max( lcs( "abc", "bghci", 3, 5 ), // These two recursive calls
lcs( "abce", "bghc", 4, 4 ) ); // cover the whole problem space
例如
(A) lcs( "abce", "bghci" ) => (B) lcs( "abc", "bghci" )
(C) lcs( "abce", "bghc" )
(B) lcs( "abc", "bghci" ) => (D) lcs( "ab", "bghci" )
(E) lcs( "abc", "bghc" )
(C) lcs( "abce", "bghc" ) => (F) lcs( "abc", "bghc" )
(G) lcs( "abce", "bgh" )
(D) lcs( "ab" , "bghci") => (H) lcs( "a" , "bghci")
(I) lcs( "ab" , "bghc" )
(E) lcs( "abc", "bghc" ) => 1 + (J) lcs( "ab" , "bgh")
(F) lcs( "abc", "bghc" ) => 1 + (K) lcs( "ab" , "bgh")
(G) lcs( "abce", "bgh" ) => (L) lcs( "abc", "bgh" )
(M) lcs( "abce", "bg" )
(H) lcs( "a", "bghci") => lcs( "", "bghci" ) (0)
(N) lcs( "a", "bghc" )
(I) lcs( "ab", "bghc") => (O) lcs( "a", "bghc" )
(P) lcs( "ab", "bgh" )
(J) lcs( "ab", "bgh" ) => (Q) lcs( "a", "bgh" )
(R) lcs( "ab", "bg" )
(K) lcs( "ab", "bgh" ) => (S) lcs( "a", "bgh" )
(T) lcs( "ab", "bg" )
(L) lcs( "abc", "bgh" ) => (U) lcs( "ab", "bg" )
(V) lcs( "abc", "bg" )
(M) lcs( "abce", "bg" ) => (W) lcs( "abc", "bg" )
(X) lcs( "abce","b" )
(N) lcs( "a", "bghc") => lcs( "", "bghc" ) (0)
(Y) lcs( "a", "bgh" )
(O) lcs( "a", "bghc" ) => lcs( "", "bghc" ) (0)
lcs( "a" "bgh" )
(P) lcs( "ab", "bgh" ) => (Z) lcs( "a", "bgh" )
(AA) lcs( "ab", "bg" )
(Q) lcs( "a", "bgh" ) => lcs( "", "bgh") (0)
(AB) lcs( "a", "bg")
(R) lcs( "ab", "bg" ) => (AC) lcs( "a", "bg")
(AD) lcs( "ab", "b" )
(S) lcs( "a", "bgh" ) => lcs( "", "bgh") (0)
(AE) lcs( "a", "bg" )
(T) lcs( "ab", "bg" ) => (AF) lcs( "a", "bg" )
(AG) lcs( "ab", "b" )
(U) lcs( "ab", "bg" ) => (AH) lcs( "a", "bg" )
(AI) lcs( "ab", "b" )
(V) lcs( "abc","bg" ) => (AJ) lcs( "ab", "bg" )
=> (AK) lcs( "abc", "b" )
(W) lcs( "abc","bg" ) => (AL) lcs( "ab", "bg" )
(AM) lcs( "abc", "b" )
(X) lcs( "abce", "b") => (AN) lcs( "abc", "b" )
lcs( "abce", "" ) (0)
(Y) lcs( "abce", "b") => (AO) lcs( "abc", "b" )
lcs( "abce", "" ) (0)
(Z) lcs( "a", "bgh") => lcs( "", "bgh" ) (0)
(AP) lcs( "a", "bg" )
(AA)lcs( "ab", "bg") => (AQ) lcs( "a", "bg" )
(AR) lcs( "ab", "b" )
(AB)lcs( "a", "bg") => lcs( "", "bg" ) (0)
(AS) lcs( "a", "b" )
(AC)lcs( "a", "bg") => lcs( "", "bg") (0)
(AT) lcs( "a", "b")
(AD)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(AE)lcs( "a", "bg") => lcs( "", "bg")
(AU) lcs( "a", "b" )
(AF)lcs( "a", "bg") => lcs( "", "bg") (0)
(AV) lcs( "a", "b")
(AG)lcs( "ab", "b" ) => 1 + lcs( "a", "" ) (1)
(AH)lcs( "a", "bg") => lcs( "", "bg") (0)
(AW) lcs( "a", "b" )
(AI)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(AJ)lcs( "ab", "bg") => (AX) lcs( "a", "bg")
(AK)lcs( "abc", "b") => (AY) lcs( "ab", "b")
lcs( "abc", "b") (0)
(AL)lcs( "ab", "bg") => (AZ) lcs( "a", "bg")
(BA) lcs( "ab", "b")
(AM)lcs( "abc", "b") => (BB) lcs( "ab", "b")
lcs( "abc", "" ) (0)
(AN)lcs( "abc", "b") => (BC) lcs( "ab", "b")
lcs( "abc", "" ) (0)
(AO)lcs( "abc", "b") => (BD) lcs( "ab", "b")
lcs( "abc", "" ) (0)
(AP)lcs( "a", "bg") => lcs( "", "bg") (0)
(BE) lcs( "a", "b")
(AQ)lcs( "a", "bg") => lcs( "", "bg") (0)
(BF) lcs( "a", "b")
(AR)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(AS)lcs( "a", "b") => lcs( "", "b") (0)
lcs( "a", "" ) (0)
(AT)lcs( "a", "b" ) as (AS)
(AU)lcs( "a", "b" ) as (AS)
(AV)lcs( "a", "b") as (AS)
(AW)lcs( "a", "b") as (AS)
(AX)lcs( "a", "bg") => lcs( "", "bg") (0)
(BG) lcs( "a", "b")
(AY)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(AZ)lcs( "a", "bg") => lcs( "", "bg") (0)
(BH) lcs( "a", "b")
(BA)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(BB)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(BC)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(BD)lcs( "ab", "b") => 1 + lcs( "a", "" ) (1)
(BE)lcs( "a", "b") as (AS)
(BF)lcs( "a", "b") as (AS)
(BG)lcs( "a", "b") as (AS)
所以 2 的 lcs 来自以下调用堆栈......
lcs( "abcde", "bghci") // (A)
lcs( "abcd", "bghci" ) // (B)
lcs( "abc", "bghc" ) // (E)
1 + lcs( "ab", "bgh" ) // (J)
lcs( "ab", "bg" ) // (R)
lcs( "ab", "b" ) // (AD)
1 + lcs( "a", "" )
给出的答案是 2。正如你所看到的，它测试了更多的组合。
我不明白的是，因为它只考虑某些子字符串 而不是所有可能的子序列，
该算法的诀窍是注意，如果第一个（或最后一个字符）相同，则最长的公共子序列是 1 + 2 个较短字符串的 lcs。像归纳证明或矛盾证明这样的东西可以帮助你证明分工是必要的，足以涵盖所有可能的替代方案。
从我的构建中可以看出，它在计算 lcs 时多次考虑了许多备选方案，因此它不是一个非常有效的算法。
评论
0赞
knightcool
5/14/2020
如果 X=“abce” 和 Y=“gbhci”，则上面的代码永远不会考虑这个子序列：第一个字符串的“bc”（从开头切掉“a”，从结尾切掉“e”）和第二个字符串的“bc”（通过切掉“g”、“h”和“i”）。但是，代码将为此输入提供正确答案。我的问题是..如何在没有直觉的情况下得出这个算法？
0赞
yogupta
5/15/2020
#2
动态编程的其中一个步骤是猜测（在YouTube上查看麻省理工学院的讲座）
您有两个指针分别指向两个字符串中的每个字符。
这里的猜测是要么包含角色，要么不包括角色。
- 如果两个字符相同，则包含该字符并将指针向前移动。
- 从字符串 X 或 Y 中选择一个字符。
max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))
它的复发情况如下：
由于您正在猜测所有可能的结果，因此上述重复给出了正确的答案。
更多参考：https://courses.csail.mit.edu/6.006/fall10/handouts/recitation11-19.pdf
评论