应用

应用1：Leetcode 300. 最长递增子序列

题目

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. 最长连续递增序列

题目

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. 最长递增子序列

题目

718. 最长重复子数组

给两个整数数组 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. 不相交的线

题目

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. 最大子序和

题目

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

应用7：Leetcode 392. 最长递增子序列

题目

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

分析

维护两个指针 \(i\)、 \(j\)，分别指向字符串 \(s\) 和 \(t\)，每次贪心地匹配：

• 如果指针 $$i、 \(j\) 指向的字符相等，则同时移动指针 \(i\)、\(j\);

• 如果指针 \(i\)、 \(j\) 指向的字符不相等，则只移动指针 \(j\);

当指针 \(j\) 遍历完字符串 \(t\) 后：

• 若指针 \(i\) 还未到达字符串 \(s\) 的末尾，则 \(s\) 不是 \(t\) 的子序列；

• 若指针 \(i\) 还未到达字符串 \(s\) 的末尾，则 \(s\) 是 \(t\) 的子序列。

代码实现

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        i, j = 0, 0
        while i < m and j < n:
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == m

应用8：Leetcode 115. 不同的子序列

题目

115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

分析

动态规划

假设字符串 \(s\) 和 \(t\) 的长度分别为 \(m\)、\(n\)，设 \(dp[i][j]\) 表示在子串 \(s[i \cdots m - 1]\) 的子序列中，子串 \(t[j \cdots n - 1]\) 出现的次数。

边界条件

当

状态转移

代码实现

应用9：Leetcode

题目

示例 1：

分析

代码实现

应用10：Leetcode

题目

示例 1：

分析

代码实现

应用11：Leetcode

题目

示例 1：

分析

代码实现

应用12：Leetcode

题目

示例 1：

分析

代码实现

应用13：Leetcode

题目

示例 1：

分析

代码实现

参考：

• 「手画图解」动态规划 思路解析 | 718 最长重复子数组

• 不相交的线

• 【宫水三叶の相信科学系列】求「最值问题」只需要确保「不漏」即可

• 最大子序和