应用
| 序号 | 题目 | 备注 |
|---|---|---|
| 1 | 300. 最长递增子序列 | |
| 2 | 674. 最长连续递增序列 | |
| 3 | 718. 最长重复子数组 | |
| 4 | 1143. 最长公共子序列 | 参考：最长公共子序列 |
| 5 | 1035. 不相交的线 | |
| 6 | 53. 最大子序和 | |
| 7 | 392. 判断子序列 | |
| 8 | 115. 不同的子序列 | |
| 9 | 583. 两个字符串的删除操作 | |
| 10 | 72. 编辑距离 | |
| 11 | 583. 两个字符串的删除操作 | |
| 12 | 647. 回文子串 | |
| 13 | 516. 最长回文子序列 |
应用1：Leetcode 300. 最长递增子序列
题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
分析
设 \(dp[i]\) 表示以 \(nums[i]\) 结尾的最长递增子序列的长度。
由于，对于以 \(nums[0]\) 结尾，并且，长度为 \(1\) 的子序列，它是一个升序序列，因此：
因此，对于任意一个以 \(num[i]\) 结尾的子序列，我们只需要在 \([0, i - 1]\) 范围内，找到最长的一个递增子序列，进行转移即可。
即我们需要在 \([0, i - 1]\) 范围内，找到一个最大的 \(dp[j]\) 进行状态转移，因此，状态转移方程为：
其中，\(dp[j]\) 表示在 \(nums[0 \cdots i - 1]\) 中，满足条件 \(nums[j] < nums[i]\)，并且，它是最大的一个。
代码实现
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1 for _ in range(len(nums))]
for i in range(len(nums)):
for j in range(0, i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
result = 0
for i in range(len(dp)):
result = max(result, dp[i])
return result
扩展
这里也可以使用二分插入的思路，进行查找插入位置。
应用2：Leetcode 674. 最长连续递增序列
题目
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
分析
方法一：贪心算法
为了得到最长连续递增序列，可以使用贪心的策略得到尽可能长的连续递增序列。
具体的做法是：
-
从左到右遍历数组；
-
将子序列的起始下标 start 设置为 0；
-
遍历数组的过程中每次比较相邻元素，
-
如果相邻元素递减，则更新起始下标 start 为当前位置；
-
否则，就起始下标就保持不变。
-
-
每遍历一个元素，就记录当前连续递增子序列的长度，同时更新最长的递增子序列长度。
方法二：双指针
维护两个指针 \(i\)、\(j\) 用于记录最长递增子序列的区间，不断移动右指针，遇到递减序列，就将左指针移动到右指针的位置，同时，记录子序列的区间长度。
代码实现
方法一
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
result = 0
n = len(nums)
start = 0
for i in range(n):
if i > 0 and nums[i] <= nums[i - 1]:
start = i
result = max(result, i - start + 1)
return result
方法二
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
n = len(nums)
result = 1
i, j = 0, 0
while i < n and j < n:
while j < n and nums[j - 1] < nums[j]:
j += 1
result = max(result, j - i)
i = j
j += 1
return result
应用3：Leetcode 300. 最长递增子序列
题目
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
分析
设 \(dp[i][j]\) 表示以 \(nums1[i - 1]\) 结尾的子数组与以 \(nums2[j - 1]\) 结尾的子数组的最长公共后缀的长度。
当两个子数组，有任意一个数组长度为 \(0\) 时，两者的公共子序列长度都为 \(0\)，因此，有：
对于任意长度的两个子数组，我们可以遍历两个子数组，对于当前元素 \(nums1[i - 1]\) 和 \(nums2[j - 1]\)：
-
如果 \(nums2[j - 1] = nums2[j - 1]\)，则说明他们可以通过，以 \(nums1[i - 2]\) 和 \(nums2[j - 2]\) 结尾的子数组转移而来，即通过状态 \(dp[i - 1][j - 1]\) 转移过来；
-
如果 \(nums2[j - 1] \ne nums2[j - 1]\)，则以 \(nums1[i - 1]\) 和 \(nums2[j - 1]\) 结尾的两个子数组公共长度为 \(0\)。
因此，状态转移方程
代码实现
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
result = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = 0
result = max(result, dp[i][j])
return result
应用4：1143. 最长公共子序列
参考：
应用5：1035. 不相交的线
题目
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
分析
这里，需要注意，题目中的两个子序列连接后不相交，必然满足子序列是两个数组的最长公共子序列，因此，题目就可以转换为求解两个数组的最长公共子序列。
动态规划
设 \(dp[i][j]\) 表示以 \(nums1[i - 1]\) 结尾的子数组与以 \(nums2[j - 1]\) 结尾的子数组的最长公共后缀的长度。
边界条件
当两个子数组，有任意一个数组长度为 \(0\) 时，两者的公共子序列长度都为 \(0\)，因此，有：
状态转移
对于任意长度的两个子数组，我们可以遍历两个子数组，对于当前元素 \(nums1[i - 1]\) 和 \(nums2[j - 1]\)：
-
如果 \(nums2[j - 1] = nums2[j - 1]\)，则说明他们可以通过，以 \(nums1[i - 2]\) 和 \(nums2[j - 2]\) 结尾的子数组转移而来，即通过状态 \(dp[i - 1][j - 1]\) 转移过来；
-
如果 \(nums2[j - 1] \ne nums2[j - 1]\)，则以 \(nums1[i - 1]\) 和 \(nums2[j - 1]\) 结尾的两个子数组公共长度为 \(0\)。
因此，状态转移方程
注意，由于 \(dp[i - 1][j - 1] \le dp[i][j - 1]\) 且 \(dp[i - 1][j - 1] \le dp[i - 1][j]\)，因此，状态转移方程可以等价于：
代码实现
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return dp[m][n]
应用6：Leetcode 53. 最大子序和
题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
分析
方法一：动态规划
假设 \(dp[i]\) 表示以元素 \(nums[i - 1]\) 结尾的最大连续数组的和，那么，我们要求的和就是每个位置的 \(dp[i]\)，然后，返回其中的最大值即可，即：
初始条件
当数组的长度为1时，显然有：
状态转移
遍历数组 \(nums\)，对于任意一个元素 \(nums[i]\) ，都有两种选择：
-
当 \(nums[i] < dp[i - 1] + nums[i - 1]\) 时，将元素 \(nums[i]\) 添加到以 \(nums[i - 1]\) 结尾的子数组的末尾；
-
当 \(nums[i] \ge dp[i - 1] + nums[i - 1]\) 时，将元素 \(nums[i]\) 单独作为一个子数组。
因此，状态转移方程为：
方法二：分治
参考：最大子序和
代码实现
方法一
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
result = nums[0]
dp = [0 for _ in range(n)]
dp[0] = nums[0]
for i in range(1, n):
if nums[i] + dp[i -1] > nums[i]:
dp[i] = nums[i] + dp[i -1]
else:
dp[i] = nums[i]
result = max(result, dp[i])
return result
【优化后的代码】：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
last = nums[0]
result = nums[0]
for i in range(1, n):
last = max(last + nums[i], nums[i])
result = max(result, last)
return result
参考：