leetcode(6)子序列系列题目
动态规划：
子序列（不连续）
（1）300. 最长递增子序列
注意：可以不连续
dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度
状态转移方程：位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
即将dp[i]更新为dp[j] + 1的最大值。
length = len(nums)
dp = [1] * length
res = 0
for i in range(length):
for j in range(i):
if(nums[i] > nums[j]):
dp[i] = max(dp[i], dp[j] + 1)
res = max(res, dp[i]) # 取最长的子序列
return res
（2）1143. 最长公共子序列
1035. 不相交的线 与本题实质上是同一个题目
注意：与 718. 最长重复子数组 的区别在于这里不要求是连续的了，但要有相对顺序，即："ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
- 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
- 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
len1, len2 = len(text1), len(text2)
# dp = [[0]*(len2 + 1) for _ in range(len1 + 1)]
dp = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]
for i in range(1, len1 + 1):
for j in range(1, len2 + 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]
子序列（连续）
（3）674. 最长连续递增序列
注意：与 300. 最长递增子序列 的区别在于这个连续，不需要两个for循环
length = len(nums)
if length == 1:
return 1
dp = [1] * length
res = 0
for i in range(1, length):#连续记录
if(nums[i] > nums[i-1]):
dp[i] = dp[i - 1] + 1
res = max(res, dp[i])
return res
（4）718. 最长重复子数组
dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
len1 = len(nums1)
len2 = len(nums2)
dp = [[0]*(len2 + 1) for _ in range(len1 + 1)] #先列再行
res = 0
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if nums1[i - 1] == nums2[j - 1]: #注意是i - 1和j - 1不是i 和 j
dp[i][j] = dp[i - 1][j - 1] + 1
res = max(res, dp[i][j]) # 取最长的子序列
return res
（5）53. 最大子数组和
这道题目的思想是： 走完这一生 如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。 我回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻
如果前边累加后还不如自己本身大，那就把前边的都扔掉，从此自己本身重新开始累加。
如果加入当前元素后的curMax<没有加之前的res,则不会添加当前元素
curMax, res = 0, nums[0]
for num in nums:
curMax = max(num, curMax + num)
res = max(res, curMax)
return res
编辑距离
（6）392. 判断子序列
注意：与 1143. 最长公共子序列 的区别是这里是判断s是否为t的子序列，即t的长度是大于等于s的。
如果s[i - 1] 与 t[j - 1]不相同，只要看s[i - 1]与 t[j - 2]的比较结果，即：dp[i][j] = dp[i][j - 1];
编辑距离的入门题目
len1, len2 = len(s), len(t)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = dp[i][j - 1]
return dp[-1][-1] == len1
（7）115. 不同的子序列
注意：与 392. 判断子序列 的区别是这里是计算在 s 的子序列中 t 出现的个数，即s的长度是大于等于t的。
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
-
当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
- 一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
- 一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
所以dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
-
当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i][j] = dp[i - 1][j];
dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
len1, len2 = len(s), len(t)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
for i in range(len1 + 1):
dp[i][0] = 1
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
（8）583. 两个字符串的删除操作
注意： 与 115.不同的子序列 的区别是两个字符串都可以删除了
dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
-
当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
-
当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
- 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
- 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
- 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
最后取最小值：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。dp[0][j]同理
len1, len2 = len(word1), len(word2)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
for i in range(len1 + 1):
dp[i][0] = i
for j in range(len2 + 1):
dp[0][j] = j
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2)
return dp[-1][-1]
（9）72. 编辑距离
注意： 与 115.不同的子序列 的区别是删除变成3种操作；与 583. 两个字符串的删除操作 的区别是只能对一个字符串，但是可以进行3种操作
-
当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
- 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
- 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1（word2添加一个元素，相当于word1删除一个元素）
- 情况三：替换操作，操作的最少次数为dp[i - 1][j - 1] + 1
最后取最小值：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;dp[0][j]同理
len1, len2 = len(word1), len(word2)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
for i in range(len1 + 1):
dp[i][0] = i
for j in range(len2 + 1):
dp[0][j] = j
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])+1
return dp[-1][-1]
贪心算法：
（2）674. 最长连续递增序列
（5）53. 最大子数组和
双指针：
（6）392. 判断子序列
参考资料：
动态规划之编辑距离总结篇