如果读者对于动态规划思路解法还不是很了解，可以查阅我之前的一篇博文《算法之【动态规划】详解》，很详细的介绍了动态规划求解思路及方法，有利于你更好的学习动态规划。
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。
示例1
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例2
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。
DP定义及状态方程
一般来说对于两个字符串类型的长度问题，都会定义一个dp[i][j]代表字符串s1[1...i]与s2[1...j]所求的问题。对于本题同样定义
dp[i][j]表示s1[1...i]和s2[1...j]的最长公共子序列为dp[i][j]。
递推方程
那么当
s1[i-1]==s2[i-1]时，dp[i][j]的最长公共子序列是在dp[i-1][j-1]的基础上加1，即dp[i][j]=dp[i-1][j-1]+1;当
s1[i-1]！=s2[i-1]时，dp[i][j]的最长公共子序列为max(dp[i][j-1], d[i-1][j])-
本题的目标值即为
dp[len(s1)-1][len(s2)-1]dp数组结构 如下图所示：
[图片上传失败...(image-e272a7-1607172884882)]注意：字符串的索引是从1开始的,0的位置代表空字符串。
初始边界条件
对于str1为空时，s2[j]均为0，即dp[0][j]=0，0=< j< len(s2);
同理 dp[i][0]=0,0 =< i < len(s1)
最终代码如下
# 动态规划
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1],dp[i-1][j])
return dp[-1][-1] #dp的最后一个数即为本题答案
附上递归形式的写法，思想其实与dp数组求解形式相同，只是需要用备忘录memo记录已经求解过的值，防止重复计算。
#递归的形式求解
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# 递归
memo = {} #备忘录
def dp(i, j):
if i == -1 or j == -1:
return 0
if (i,j) in memo:
return memo[(i,j)]
if text1[i] == text2[j]:
memo[(i,j)] = dp(i-1, j-1) + 1
else:
memo[(i,j)] = max(dp(i-1, j), dp(i,j-1))
return memo[(i,j)]
return dp(len(text1)-1,len(text2)-1)
如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
