擅长:python、mysql、java
<p>但是。。您已经知道术语“最长公共子序列”,并且可以找到许多关于动态规划算法的描述。<br/>
<a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow noreferrer">Wiki link</a></p>
<p>伪码</p>
<pre><code>function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j] //i-1 and j-1 if reading X & Y from zero
C[i,j] := C[i-1,j-1] + 1
else
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]
function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
if i = 0 or j = 0
return ""
if X[i] = Y[j]
return backtrack(C, X, Y, i-1, j-1) + X[i]
if C[i,j-1] > C[i-1,j]
return backtrack(C, X, Y, i, j-1)
return backtrack(C, X, Y, i-1, j)
</code></pre>