动态规划简明教程 - 4
❓ 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
# 示例来自: https://leetcode.cn/
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
💡 解题过程
动态规划的子问题分解属于自顶向下的思想，和前面几篇系列文章一样，这道题也可以按照 暴力搜索 -> 记忆化搜索 -> 动态规划搜索 的顺序来实现代码，这样循序渐进地优化更符合我们的思考过程，也可以降低我们从一开始直接推导状态转移方程的心理压力。
接下来，我们先尝试着给出一个可行的题解，然后在这个基础上慢慢迭代优化。
解题方法函数原型:
func lengthOfLIS(nums []int) int {}
单元测试
为了节省篇幅，这里给出针对本题的单元测试代码，不管 暴力搜索 -> 记忆化搜索 -> 动态规划搜索 哪种实现方式，都可以直接运行该单元测试。
func Test_lengthOfLIS(t *testing.T) {
type args struct {
nums []int
}
tests := []struct {
name string
args args
want int
}{
{
"test-1",
args{nil},
0,
},
{
"test-2",
args{[]int{1}},
1,
},
{
"test-3",
args{[]int{10, 9, 2, 5, 3, 7, 101, 18}},
4,
},
{
"test-4",
args{[]int{0, 1, 0, 3, 2, 3}},
4,
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := lengthOfLIS(tt.args.nums); got != tt.want {
t.Errorf("lengthOfLIS() = %v, want %v", got, tt.want)
}
})
}
}
💪 暴力搜索
解题思路
暴力搜索的思路是尝试找出所有可能的递增子序列，然后找出其中最长的那个，具体的算法步骤可以概括为:
- 遍历数组中每个元素
- 针对每个当前元素，尝试找出以该元素开头的所有递增子序列
- 计算将当前元素包含在子序列中时，可以获得的最大递增子序列长度
- 计算跳过当前元素时 (也就是不将当前元素包含在子序列中)，可以获得的最大递增子序列长度
- 重复第 2, 3, 4 步骤，同时更新已知的最大递增子序列长度，直到数组遍历完成
暴力搜索示例
遍历到数组的任意一个元素时，我们有两种选择:
- 将当前元素添加到已有的子序列中
- 跳过当前元素，将当前元素的下一个元素添加到已有的子序列中
例如遍历第一个元素 1 时，存在的两种选择:
- 将
1加入到子序列中，已知的最大递增子序列长度为 2 - 跳过
1，已知的最大递增子序列长度为 1
实现代码
因为需要 尝试数组中每个元素的所有可能子序列长度 (穷举)，所以自然而然，我们会想到使用回溯算法来实现代码。
根据解题思路，可以写出如下的代码:
// 题解代码
// 暴力搜索迭代版本 (超时)
// 超时原因: 重复检测
func lengthOfLISBruteForce(nums []int) int {
if len(nums) == 0 {
return 0
}
maxLen := 1
backtrack(nums, -1, 0, &maxLen)
return maxLen
}
// 回溯穷举每个元素开头的所有递增子序列
// prev: 上个元素的索引
// cur: 当前元素的索引
func backtrack(nums []int, prev, cur int, maxLen *int) int {
if cur == len(nums) {
return 0
}
taken := 0
if prev == -1 || nums[cur] > nums[prev] {
// 计算将当前元素包含在子序列中时
// 可以获得的最大递增子序列长度
taken = 1 + backtrack(nums, cur, cur+1, maxLen)
}
// 计算跳过当前元素时 (也就是不将当前元素包含在子序列中)
// 可以获得的最大递增子序列长度
notTaken := backtrack(nums, prev, cur+1, maxLen)
// 更新已知的最大递增子序列长度
*maxLen = max(*maxLen, max(taken, notTaken))
return max(taken, notTaken)
}
提交超时
运行单元测试:
$ go test -v -count=1 .
输出结果如下:
=== RUN Test_lengthOfLIS
=== RUN Test_lengthOfLIS/test-1
=== RUN Test_lengthOfLIS/test-2
=== RUN Test_lengthOfLIS/test-3
=== RUN Test_lengthOfLIS/test-4
--- PASS: Test_lengthOfLIS (0.00s)
--- PASS: Test_lengthOfLIS/test-1 (0.00s)
--- PASS: Test_lengthOfLIS/test-2 (0.00s)
--- PASS: Test_lengthOfLIS/test-3 (0.00s)
--- PASS: Test_lengthOfLIS/test-4 (0.00s)
PASS
ok leetcode/0300-Longest-Increasing-Subsequence 0.002s
单元测试全部通过，表面上来看，我们的暴力搜索实现没有问题，现在去官方提交看看运行结果。
提交代码到官方后，提示 “测试超出时间限制”，说明代码的运行时间复杂度太高了，也就是代码运行时间存在优化空间。
超时原因分析
在尝试优化暴力搜索之前，我们先来分析一下刚才的算法为何时间复杂度很高。
对于数组中的每个元素，我们都要检测从其位置开始到数组结尾的最大递增子序列长度，这会产生一个问题: 元素重复检测，也就是因为 “重叠子问题” 导致的 子问题重复计算。
举例来说，遍历第一个元素 nums[1] = 1 (0, 1) 时，在回溯 (递归) 过程中会依次检测会出现两条路径:
- 将当前元素添加到已有的子序列中，递归检测
(0, 1) - 跳过当前元素，将当前元素的下一个元素添加到已有的子序列中，递归检测
(0, 2)
然而无论哪条路径，都会重复检测 (2, 3) 这个元素组合，以此类推，随着递归的深度不断增加，重复检测的元素组合会越来越多。
📝 记忆化搜索
现在我们已经分析出了暴力搜索的超时原因 (子问题重复计算)，和 Fibonacci 问题类似，作为优化方案，可以采用一个 额外的备忘录 来记录已经检测过的元素组合，具体来说:
- 回溯 (递归) 过程中检测每个元素的不同路径组合时 (也就是不同的
prev + cur参数组合) - 如果当前路径已经检测过，直接返回备忘录中的值即可
- 如果当前路径未检测过，进行递归检测，并在递归结束后将对应的值添加到备忘录中
下面是对应的实现代码:
// 记忆化搜索
func lengthOfLISMemo(nums []int) int {
if len(nums) == 0 {
return 0
}
// 初始化备忘录
// 所有值设置为 -1
// 表示当前元素组合还未被检测
// 使用一个二维数组来表示 HashMap
// 其中 memo[i][j] 表示:
// i = 参数 prev + 1 (prev 从 -1 开始)
// j = 参数 cur
memo := make([][]int, len(nums))
for i := range memo {
memo[i] = make([]int, len(nums)+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
return backtrackMemo(nums, -1, 0, memo)
}
func backtrackMemo(nums []int, prev, cur int, memo [][]int) int {
// 递归结束条件
if cur == len(nums) {
return 0
}
// 如果备忘录中已经包含 [当前元素组合]
// 直接返回
if memo[prev+1][cur] != -1 {
return memo[prev+1][cur]
}
taken := 0
if prev == -1 || nums[cur] > nums[prev] {
// 计算将当前元素包含在子序列中时
// 可以获得的最大递增子序列长度
taken = 1 + backtrackMemo(nums, cur, cur+1, memo)
}
// 计算跳过当前元素时 (也就是不将当前元素包含在子序列中)
// 可以获得的最大递增子序列长度
notTaken := backtrackMemo(nums, prev, cur+1, memo)
// 更新备忘录中 [当前元素组合] 的值
memo[prev+1][cur] = max(taken, notTaken)
return memo[prev+1][cur]
}
虽然加了备忘录之后代码性能依然较低，但是好在可以通过全部的测试用例了。
代码执行过程示例
如图所示，有了备忘录之后，每个元素组合只会被计算一次，计算量会大大减少。
举例来说，当递归计算元素组合 [0, 1] 时 (prev = 0, cur = 1)，会出现两个组合 (路径):
- 将当前元素添加到已有的子序列中，对应组合
[1, 2] - 跳过当前元素，将当前元素的下一个元素添加到已有的子序列中，对应组合
[0, 2]
接下来，递归计算组合 [1, 2] 时，会计算其子组合 [2, 3] 和 [1, 3] 并在计算完成后更新到备忘录中。
在递归计算组合 [0, 2] 时，也会计算子组合 [2, 3]，因为 [2, 3] 之前已经计算过了，所以直接从备忘录中取得计算结果即可，无需重复计算。
🚀 动态规划
现在实现了暴力搜索和记忆化搜索代码之后，我们来思考如何编写动态规划代码。
状态转移方程
设计正确的状态转移方程是解决动态规划问题的前提。
自顶向下时，当前元素作为 “当前子序列的末尾元素”，可以选择加入或者不加入到子序列中
自底向上时，根据已知的子序列状态，将当前元素作为 “已知的子序列状态” 末尾元素，计算可以得到的子序列长度，(和自顶向下正好相反)
和前文中暴力搜索和记忆化搜索的 自顶向下 的实现不同，对于动态规划，我们考虑如何 自定向上 的实现。
遍历数组时，对于每个当前元素 nums[i]，我们需要存储以 nums[i] 为结尾可以形成的最大递增子序列长度，记录为 dp[i] 。
这样在向后遍历其他元素时，每次只需要根据已有的子问题解 dp[...] 来计算出当前元素 dp[i] 的解即可，具体来说：
nums[i]默认为 1，表示由其自身构成的最大递增子序列长度- 遍历
nums[0] ... nums[i], 每个当前元素记录为nums[j]，执行下列操作:- 如果
nums[j] >= nums[i], 说明nums[i]连接nums[j]时 无法形成递增子序列，直接跳过即可 - 如果
nums[j] < nums[i], 说明nums[i]连接nums[j]时 可以形成递增子序列，此时更新dp[i]对应的最大长度解，也就是dp[i](当前值) 和dp[j] + 1(连接nums[j]之后) 中的较大值
- 如果
举例来说:
以 nums[0] = 0 构成的最大递增子序列长度为 1 (0)，当遍历到下一个元素 nums[1] = 1 时，因为 nums[0] < nums[1], 可以形成递增子序列，此时将 nums[1] = 1 可以构成的最大递增子序列长度更新为 2 (0, 1)。
同理，以 nums[1] = 1 构成的最大递增子序列长度为 2 (0, 1)，当遍历到下一个元素 nums[2] = 0 时，因为 nums[2] >= nums[1], 无法形成递增子序列，直接跳过即可。
根据这两个示例和边界条件，可以推导出如下的状态转移方程:
$$ \begin{align*} F(i) = \begin{cases} \max\ ( F(i), F(j) + 1 \ ) \ & \text {, } \text{F}(j) < F(i), j \in [0:i) \\ 1 & \text{, } \text{}default \end{cases} \end{align*} $$
算法步骤
根据上面的分析过程和状态转移过程，可以得到如下的算法步骤：
- 定义问题状态：计算数组中以每个元素结尾的最长子序列长度
- 状态转移方程：
F(i) = max{F(i), F(j) + 1} - 初始化：建立状态转移表 (一维数组)
- 计算子问题：计算子数组
nums[0:i]中以每个元素结尾的最长子序列长度 - 计算原问题：计算以当前元素的结尾的最长子序列长度
实现代码
计算出状态转移方程之后，剩下的事情就是将算法步骤直接翻译为代码就可以了，下面的是动态规划的实现代码。
// 动态规划
func lengthOfLIS(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
maxLen := 0
// dp[i] 的值代表以 nums[i] 结尾的最长子序列长度
dp := make([]int, n)
for i := 0; i < n; i++ {
// 默认为 1
dp[i] = 1
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j]+1)
}
}
maxLen = max(maxLen, dp[i])
}
return maxLen
}
下面是动态规划代码的执行过程图解。
