题目链接
https://leetcode-cn.com/problems/longest-common-subsequence/
题目介绍
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
classSolution:deflongestCommonSubsequence(self, t1: str, t2: str) -> int:memo = {}defdp(i, j):# 查表if(i, j)inmemo:returnmemo[(i, j)]# base caseifi ==-1orj ==-1:return0ift1[i] == t2[j]: memo[(i, j)] = dp(i -1, j -1) +1else: memo[(i, j)] = max(dp(i, j -1), dp(i -1, j))returnmemo[(i, j)] m, n = len(t1) -1, len(t2) -1returndp(m, n)
思路
首先，拿到本题，脑海里应该有一个解题大框架，你看到子序列就应该想到这题大概率需要用到两个指针i，j 分别指向字符串某个位置，然后按一定规律朝某一方向延申，还记得上次的编辑距离吗？思路其实差不多，两个指针，然后不同情况直接max对抗
本题分为三种情况
1. 两个指针所指位置对应字符相等，这个很简单，说明已经找到一个了，总数即为1 + dp(i-1,j- 1)
2. 举个例子，如s1 = "bpd",s2 = "ebi" 这个时候我们想象这两个都是数轴，是不是把s2往左边拉一个，这样两个是不是又可以相等了,就是dp(i,j-1) 类似的，若s1 = "bpd",s2 = "poi" 这个时候，把s1往左边拉一个就行，就是dp(i-1,j)
是不是轻轻松松，本题就解决了，根本不费吹灰之力，就把这题解决，这就告诉我们学算法题学的是框架，思路，而不是只会一道题
但是，这是最优解吗？当然不是，我们在斐波那契数列已经讲过，你重复迭代函数肯定时间复杂度高，那么我们就要想如何来重复写表来降低复杂度
classSolution:deflongestCommonSubsequence(self, t1: str, t2: str) -> int:m, n = len(t1), len(t2)# 构建DP TABLE + base casedp = [[0] * (n +1)for_inrange(m +1)]foriinrange(1, m +1):forjinrange(1, n +1):ift1[i -1] == t2[j -1]: dp[i][j] = dp[i -1][j -1] +1else: dp[i][j] = max(dp[i -1][j], dp[i][j -1])returndp[-1][-1]
思路
本题关于dp[i][j] 的定义是*s1[0:i],s2[0:j]*两者的最长公共序列长度，当i,j都等于0时，自然为0，这也是为什么i,j从1开始，本质上遍历的范围还是整个字符
本题分为三种情况
1. 两个指针所指位置对应字符相等，这个很简单，说明已经找到一个了，总数即为1 + dp[i-1][j- 1]
2. 举个例子，如s1 = "bpd",s2 = "ebi" 这个时候我们想象这两个都是数轴，是不是把s2往左边拉一个，这样两个是不是又可以相等了,就是dp[i,j-1] 类似的，若s1 = "bpd",s2 = "poi" 这个时候，把s1往左边拉一个就行，就是dp[i-1,j]
3. 万一都不相等怎么办，它题目说要求最长，你都不相等，能是最长吗？直接舍去
注意点
一开始的列表生成就应该有人写成
dp = [[0] * (n +1)] * (m +1)
然后说明明生成都一样，可结果就是报错，python生成一维数组这样做没问题，可如果上升到二维，它会把里面的看成一个整体，简单说来就是你改大家改
dp = [[0] *2] *2dp[0][0] =1print(dp)#[[1,0],[1,0]]
奇怪的是我只想改一个，结果都变了
正确生成二维数组需要这样写
dp = [[0] * (n +1)for_inrange(m +1)]
大家觉得有帮助的可以去我的github主页，那里有更新更全面的题解
https://github.com/sherlcok314159/leetcode-python-3/blob/main/md/all_have.md
