leetcode第1143题
这里选择利用动态规划的方法进行解决，两个字符串选择利用二维数组进行解决（对于两个字符串的动态规划问题，一般而言都需要一个二维dp数组）
text2 = 'babcde' text1 = 'ace'
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | ||
| ” “ | b | a | b | c | d | e | ||
| 0 | “ ” | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | a | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | c | 0 | 0 | 1 | 1 | 2 | 2 | 2 |
| 3 | e | 0 | 0 | 1 | 1 | 2 | 2 | 3 |
至于为什么要在每个字符串前面插入一个空字符，个人理解是为了在实现算法时利用到检索周围的数据，为了更加简单才特意这样做的。也就是说对于text1[0]和text[0]来说它们的最长公共子序列（LCS）就是dp[1][1],反过来说就是dp[2][4]=2的含义就是对于‘ac’和‘babc’，它们的LCS长度为2。
具体代码如下：
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
def dp(i,j):
if i ==-1 or j ==-1:
return 0
if text1[i]==text2[j]:
return dp(i-1,j-1)+1
else:
return max(dp((i-1),j),dp(i,(j-1)))
return dp(len(text1)-1,len(text2)-1)
上述代码是利用递归实现，所以时间复杂度过高，不能通过测试要求，因此之后可以利用备忘录的形式将数据保存下来避免多余计算，减少时间复杂度。
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1) #列
n = len(text2) #行
dp = [[0] * (m+1) for _ in range(n+1)] #避免在同一行进行操作
#我们知道一维数组可以用 [0] * N 这种声明方式。但是二维数组不能用上面的声明方式，这会导致
#dp 中的每行的列表是同一个 id，所以对其中一行的操作都会表现为每一行的操作
for i in range(1,n+1):
for j in range(1,m+1):
if text1[j-1]==text2[i-1]:
print(text2[i-1],text1[j-1])
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i][j-1],dp[i-1][j])
print(dp)
return dp[n][m]
在书写上述代码时遇到一个问题，这里记录下来，在python中形成二维数组时不能按照形成一维数组的套路来形成一维数组，这样会使得每次都是在同一行上进行计算，从而返回错误结果。需要使用for循环进行产生二维数组才是正确的数组。
对于动态规划问题个人也是才刚刚开始学习，这里用来记录一些个人遇到的问题。
