最长公共子序列

最长公共子序列问题

问题描述：

给定两个字符串s1s2s3…sn和t1t2t3…tm，求出这两个字符串最长的公共子序列（LCS,longest Common Subsequence 最长公共子序列问题）,例如：

输入
n = 4
m = 4
s = ‘abcd’
t = ‘becd’

输出：
3（’bcd’)

---

解析：

定义：

dp[i][j] := a1...ai和b1...b[j]的最长公共子序列LCS数

由此，s1…si+1和t1…tm+1的子序列可能是：

1. 当s1+1等于tj+1时，等于在si和tj公共列表后加si+1
2. 或者等于Si+1和tj之间的LCS
3. 或者等于si和tj+1之间的LCS

即可推出递推关系：

dp[i+1][j+1] = dp[i][j] + 1 （第1点）

dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]) （2和3点）

---

代码：

n,m,a,b = 5,6,'bcdef','bcdevf'
dp = [[0 for _ in range(m+1)] for j in range(n+1)]
def DP():
    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                dp[i+1][j+1] = dp[i][j]+1
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])  #没有匹配上的两种情况
    print(dp[n][m])
DP()