02-14 18:38
文件名称:
动态规划设计：最长递增子序列.md
所在目录:
docs / 算法 / 刷题套路 / 动态规划系列
文件大小:
9.28 KB
下载地址:
文本预览:
# 动态规划设计：最长递增子序列
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
* [300.最长上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence)
也许有读者看了前文，学会了动态规划的套路：找到了问题的「状态」，明确了 `dp` 数组/函数的含义，定义了 base case；但是不知道如何确定「选择」，也就是不到状态转移的关系，依然写不出动态规划解法，怎么办？
不要担心，动态规划的难点本来就在于寻找正确的状态转移方程，本文就借助经典的「最长递增子序列问题」来讲一讲设计动态规划的通用技巧：**数学归纳思想**。
最长递增子序列（Longest Increasing Subsequence，简写 LIS）是非常经典的一个算法问题，比较容易想到的是动态规划解法，时间复杂度 O(N^2)，我们借这个问题来由浅入深讲解如何找状态转移方程，如何写出动态规划解法。比较难想到的是利用二分查找，时间复杂度是 O(NlogN)，我们通过一种简单的纸牌游戏来辅助理解这种巧妙的解法。
先来看一下题目，很容易理解:
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。下面先来一步一步设计动态规划算法解决这个问题。
## 动态规划解法
**动态规划的核心设计思想是数学归纳法。**
相信大家对数学归纳法都不陌生，高中就学过，而且思路很简单。比如我们想证明一个数学结论，那么我们先假设这个结论在 `k
我们直接拿最长递增子序列这个问题来举例，不过首先要定义清楚 dp 数组的含义，即 `dp[i]` 的值到底代表什么?
**我们这样定义：`dp[i]` 表示以 `nums[i]` 这个数结尾的最长递增子序列的长度。**
举个例子：
算法演进的过程是这样的：
根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。
```java
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
```
大家也许会问，刚才这个过程中的每个 `dp[i]` 的结果都是我们肉眼看出来的，我们应该怎样设计算法逻辑来正确计算每个 `dp[i]` 呢?
这就是动态规划的重头戏了，要思考如何进行状态转移，这里就可以使用数学归纳的思想：
我们已经知道了 `dp[0-4]` 的所有结果，我们如何通过这些一直结果推出 `dp[5]` 呢？
根据我们刚才对 dp 数组的定义，现在想求 `dp[5]` 的值，也就是相求以 `nums[5]` 为结尾的最长递增子序列。
`nums[5] = 3` 既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加以。
当然，可能形成很多中心的子序列，但是我们只要最长的，把最长的子序列的长度作为 `dp[5]` 的值即可。
类似数学归纳法，你已经可以通过 dp[0...4] 算出 dp[5] 了，那么任意 dp[i] 你肯定都可以算出来：
还有一个细节问题，就是 base case。dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1.下面我们看一下完整代码:
至此，这道题就解决了，时间复杂度 `O(n^2)` 。总结一下动态规划的设计流程:
首先明确 dp 数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
然后根据 dp 数组的定义，运用数学归纳法的思想，假设`dp[0 ~ i - 1]` 都已知，想办法求出 `dp[i]`，一旦这一步完成，整个题目基本就解决了。
但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。
## 二分查找解法
这个解法的时间复杂度会降为 `O(NlogN)` ，但说实话，正常人基本想不到这种解法（也许玩过某些纸牌游戏的人可以想出来）。所以如果大家了解一下就好，正常情况下能够给出动态规划解法就已经很不错了。
根据题目的意思，我都很难想象这个问题竟然能和二分查找扯上关系。其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关，甚至有一种排序方法就叫做 patience sorting（耐心排序）。
为了简单起见，后文跳过所有数学证明，通过一个简化的例子来理解一下思路。
首先，给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。
处理这些扑克牌要遵循以下规则：
只能把点数小的牌压到点数比它大的牌上。如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去。如果当前牌有多个堆可供选择，则选择最左边的堆放置。
比如说上述的扑克牌最终会被分成这样 5 堆（我们认为 A 的值是最大的，而不是 1）。
为什么遇到多个可选择堆的时候要放到最左边的堆上呢？因为这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q），证明略。
按照上述规则执行，可以算出最长递增子序列，牌的堆数就是我们想求的最长递增子序列的长度，证明略。
我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗，牌堆顶的牌不是有序吗，这就能用到二分查找了：用二分查找来搜索当前牌应放置的位置。
PS：旧文 [二分查找算法详解](http://mp.weixin.qq.com/s?__biz=MzU0MDg5OTYyOQ==&mid=2247484090&idx=1&sn=5635cf1c4fd8a8570b63c7ae9b4304c2&chksm=fb3362f8cc44ebee0a19a4cfba7f2e13923e05f47e15f2e99a1f42b01aeee83b946aceac3d4c&scene=21#wechat_redirect) 详细介绍了二分查找的细节及变体，这里就完美应用上了。如果没读过强烈建议阅读。
至此，二分查找的解法也讲解完毕。
这个解法确实很难想到。首先涉及数学证明，谁能想到按照这些规则执行，就能得到最长递增子序列呢？其次还有二分查找的运用，要是对二分查找的细节不清楚，给了思路也很难写对。
所以，这个方法作为思维拓展好了。但动态规划的设计方法应该完全理解：假设之前的答案已知，利用数学归纳的思想正确进行状态的推演转移，最终得到答案。
读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
* [300.最长上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence)
也许有读者看了前文，学会了动态规划的套路：找到了问题的「状态」，明确了 `dp` 数组/函数的含义，定义了 base case；但是不知道如何确定「选择」，也就是不到状态转移的关系，依然写不出动态规划解法，怎么办？
不要担心，动态规划的难点本来就在于寻找正确的状态转移方程，本文就借助经典的「最长递增子序列问题」来讲一讲设计动态规划的通用技巧：**数学归纳思想**。
最长递增子序列（Longest Increasing Subsequence，简写 LIS）是非常经典的一个算法问题，比较容易想到的是动态规划解法，时间复杂度 O(N^2)，我们借这个问题来由浅入深讲解如何找状态转移方程，如何写出动态规划解法。比较难想到的是利用二分查找，时间复杂度是 O(NlogN)，我们通过一种简单的纸牌游戏来辅助理解这种巧妙的解法。
先来看一下题目，很容易理解:
注意「子序列」和「子串」这两个名词的区别，子串一定是连续的，而子序列不一定是连续的。下面先来一步一步设计动态规划算法解决这个问题。
## 动态规划解法
**动态规划的核心设计思想是数学归纳法。**
相信大家对数学归纳法都不陌生，高中就学过，而且思路很简单。比如我们想证明一个数学结论，那么我们先假设这个结论在 `k
我们直接拿最长递增子序列这个问题来举例，不过首先要定义清楚 dp 数组的含义，即 `dp[i]` 的值到底代表什么?
**我们这样定义：`dp[i]` 表示以 `nums[i]` 这个数结尾的最长递增子序列的长度。**
举个例子：
算法演进的过程是这样的：
根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。
```java
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
```
大家也许会问，刚才这个过程中的每个 `dp[i]` 的结果都是我们肉眼看出来的，我们应该怎样设计算法逻辑来正确计算每个 `dp[i]` 呢?
这就是动态规划的重头戏了，要思考如何进行状态转移，这里就可以使用数学归纳的思想：
我们已经知道了 `dp[0-4]` 的所有结果，我们如何通过这些一直结果推出 `dp[5]` 呢？
根据我们刚才对 dp 数组的定义，现在想求 `dp[5]` 的值，也就是相求以 `nums[5]` 为结尾的最长递增子序列。
`nums[5] = 3` 既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加以。
当然，可能形成很多中心的子序列，但是我们只要最长的，把最长的子序列的长度作为 `dp[5]` 的值即可。
类似数学归纳法，你已经可以通过 dp[0...4] 算出 dp[5] 了，那么任意 dp[i] 你肯定都可以算出来：
还有一个细节问题，就是 base case。dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1.下面我们看一下完整代码:
至此，这道题就解决了，时间复杂度 `O(n^2)` 。总结一下动态规划的设计流程:
首先明确 dp 数组所存数据的含义。这步很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
然后根据 dp 数组的定义，运用数学归纳法的思想，假设`dp[0 ~ i - 1]` 都已知，想办法求出 `dp[i]`，一旦这一步完成，整个题目基本就解决了。
但如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。
## 二分查找解法
这个解法的时间复杂度会降为 `O(NlogN)` ，但说实话，正常人基本想不到这种解法（也许玩过某些纸牌游戏的人可以想出来）。所以如果大家了解一下就好，正常情况下能够给出动态规划解法就已经很不错了。
根据题目的意思，我都很难想象这个问题竟然能和二分查找扯上关系。其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关，甚至有一种排序方法就叫做 patience sorting（耐心排序）。
为了简单起见，后文跳过所有数学证明，通过一个简化的例子来理解一下思路。
首先，给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。
处理这些扑克牌要遵循以下规则：
只能把点数小的牌压到点数比它大的牌上。如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去。如果当前牌有多个堆可供选择，则选择最左边的堆放置。
比如说上述的扑克牌最终会被分成这样 5 堆（我们认为 A 的值是最大的，而不是 1）。
为什么遇到多个可选择堆的时候要放到最左边的堆上呢？因为这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q），证明略。
按照上述规则执行，可以算出最长递增子序列，牌的堆数就是我们想求的最长递增子序列的长度，证明略。
我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗，牌堆顶的牌不是有序吗，这就能用到二分查找了：用二分查找来搜索当前牌应放置的位置。
PS：旧文 [二分查找算法详解](http://mp.weixin.qq.com/s?__biz=MzU0MDg5OTYyOQ==&mid=2247484090&idx=1&sn=5635cf1c4fd8a8570b63c7ae9b4304c2&chksm=fb3362f8cc44ebee0a19a4cfba7f2e13923e05f47e15f2e99a1f42b01aeee83b946aceac3d4c&scene=21#wechat_redirect) 详细介绍了二分查找的细节及变体，这里就完美应用上了。如果没读过强烈建议阅读。
至此，二分查找的解法也讲解完毕。
这个解法确实很难想到。首先涉及数学证明，谁能想到按照这些规则执行，就能得到最长递增子序列呢？其次还有二分查找的运用，要是对二分查找的细节不清楚，给了思路也很难写对。
所以，这个方法作为思维拓展好了。但动态规划的设计方法应该完全理解：假设之前的答案已知，利用数学归纳的思想正确进行状态的推演转移，最终得到答案。
点赞
回复
X