Leetcode Link: 剑指 Offer II 095. 最长公共子序列 - 力扣（LeetCode）
题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
从暴力递归到动态规划
问题分解：考虑 text1[0...i] 和 text2[0...j] 这两段，最长公共子序列是多长？
那么对应这个问题，一共有 4 种情况（考虑当前结尾存在哪些可能性）：
- 当前两个公共子序列，一定不以 i 和 j 结尾
- 一定以 i 结尾，一定不以 j 结尾
- 一定不以 i 结尾，一定以 j 结尾
- 一定同时以 i, j 结尾（有前提）
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
return self.process(text1, text2, len(text1)-1, len(text2)-1)
# text1[0 .. i]
# text2[0 .. j]
# 返回最长公共子序列
def process(self, text1, text2, i, j):
# 有任何一个没了，都说明当前肯定没有公共子序列
if i < 0 or j < 0:
return 0
# 公共子序列一定不以 i, j结尾
p1= self.process(text1, text2, i-1, j-1)
# 一定以 i结尾, 一定不以j结尾
p2 = self.process(text1, text2, i, j-1)
# 一定不以 i 结尾, 一定以 j 结尾
p3 = self.process(text1, text2, i-1, j)
# 一定以i, j 结尾(有前提条件，相等才行)
p4 = 0
if text1[i] == text2[j]:
p4 = self.process(text1, text2, i-1, j-1) + 1
return max(p1, p2, p3, p4)
有重复吗？
像本题，是在四个情况中求 max，即使有重复，最后也不会影响 max 的值，但是如果有类似的问题，最后需要四个情况相加，答案还正确吗？
应该是有重复的，譬如 2、3 条，如果“必须”以某一位结尾，可能需要遍历另一个，保证另一个里面有当前这个结尾的字符才可能进入这个情况。 在老师的课程中，他说只有2、3、4三种情况，2、3不再是“一定”，而是“可以”考虑，两者的重叠是1。
动态规划
显然，只和 i, j 有关，可以写成二维 dp 表
请一定仔细分析位置依赖，任意位置依赖的是上、左、左上。 我开始还tm要反对角线填写！实际上从上到下一行一行写就行！
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for _ in range(len(text2))] for _ in range(len(text1))]
# base case 不用写，范围外。可以放到if里
# 仔细分析，从上到下一行一行写就行
for i in range(len(text1)):
for j in range(len(text2)):
p1 = p2 = p3 = 0
if i - 1 >= 0:
p2 = dp[i-1][j]
if j - 1 >= 0:
p3 = dp[i][j-1]
p4 = 0 if text1[i] != text2[j] else 1
if i - 1 >= 0 and j - 1 >= 0:
p1 = dp[i-1][j-1]
p4 += dp[i-1][j-1]
dp[i][j] = max(p1,p2,p3,p4)
return dp[len(text1)-1][len(text2)-1]动态规划（状态压缩）
可以看到，当前行只和上一行有关，因此压缩至2个一维 dp
但是要注意同时和 [i-1][j-1], [i][j-1] 有关，如果只使用一个一维的，会导致覆盖的情况，所以需要 2 个一维 dp 来保存上下两行。
如果使用一维的，当更新到j时候(一维，肯定是不要行，即不要i),j-1已经更新了，所以我们没法获取到左上的值了，只能获取到左边的值
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp0 = [0 for _ in range(len(text2))] # 上一行
dp1 = [0 for _ in range(len(text2))] # 当前行
# base case 不用写，范围外。可以放到if里
# 仔细分析，从上到下一行一行写就行
for i in range(len(text1)):
for j in range(len(text2)):
p1 = p2 = p3 = 0
p2 = dp0[j] # 依赖上，这里不需要考虑i越界了，因为即使越界我们也有dp0
p4 = 0 if text1[i] != text2[j] else 1
if j - 1 >= 0: # 这里合并了，不用判断i-1越界了
p3 = dp1[j-1] # 依赖左
p1 = dp0[j-1] # 依赖左上
p4 += dp0[j-1] # 依赖左上
dp1[j] = max(p1,p2,p3,p4)
# 当前行变成上一行进入下一次循环
dp0, dp1 = dp1, dp0
return dp0[len(text2)-1]启发和联系
关于上面提到的重复的那个疑问，可以看看这个类似的题，但是本质有点区别：不同的子序列