动态规划问题-LCS

LCS 最长公共子序

如下

x = list("GCCCTAGCGDE")
y = list("GCGCAATGDE")

x 和 y 的最长公共子序长度为为 7

公式

WechatIMG41.jpeg

实现

401620383230_.pic_hd.jpg

代码

x = list("GCCCTAGCGDE")
y = list("GCGCAATGDE")

def dp(i, j):
    if i == -1 or j == -1:
        return 0
    if x[i] == y[j]:
        return dp(i-1, j-1) + 1
    return max(dp(i-1, j), dp(i, j-1))

print(dp(len(x)-1, len(y)-1))