前缀型动态规划
def longest_common_seq(s1, s2):
if not s1 or not s2:
return
m, n = len(s1), len(s2)
# dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]),当前字符依赖于i-1和j-1,需要补一个状态零
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]: # 切记字符串的第i个字符是i-1
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
longest_common_seq("deng", "de")
标签：return,seq,s2,s1,range,公共,序列,最长,dp From： https://www.cnblogs.com/demo-deng/p/16589885.html