【算法】五分钟算法小知识:动态规划设计:最长递增子序列-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

【算法】五分钟算法小知识:动态规划设计:最长递增子序列

2020-05-11 07:22:50 668 1

最长递增子序列(Longest Increasing Subsequence,简写 LIS)是比较经典的一个问题,比较容易想到的是动态规划解法,时间复杂度 O(N^2),我们借这个问题来由浅入深讲解如何写动态规划。

比较难想到的是利用二分查找,时间复杂度是 O(NlogN),我们通过一种简单的纸牌游戏来辅助理解这种巧妙的解法。

先看一下题目,很容易理解:

1.jpg

注意「子序列」和「子串」这两个名词的区别,子串一定是连续的,而子序列不一定是连续的。下面先来一步一步设计动态规划算法解决这个问题。

一、动态规划解法

动态规划的核心设计思想是数学归纳法

相信大家对数学归纳法都不陌生,高中就学过,而且思路很简单。比如我们想证明一个数学结论,那么我们先假设这个结论在 k<n 时成立,然后想办法证明 k=n 的时候此结论也成立。如果能够证明出来,那么就说明这个结论对于 k 等于任何数都成立。

类似的,我们设计动态规划算法,不是需要一个 dp 数组吗?我们可以假设 dp[0...i−1] 都已经被算出来了,然后问自己:怎么通过这些结果算出dp[i] ?

直接拿最长递增子序列这个问题举例你就明白了。不过,首先要定义清楚 dp 数组的含义,即 dp[i] 的值到底代表着什么?

我们的定义是这样的:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度

举个例子:

2.jpg

3.jpg

算法演进的过程是这样的:

03.gif

根据这个定义,我们的最终结果(子序列的最大长度)应该是 dp 数组中的最大值。

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] 呢?

4.jpg

根据刚才我们对 dp 数组的定义,现在想求 dp[5] 的值,也就是想求以 nums[5] 为结尾的最长递增子序列。

nums[5] = 3,既然是递增子序列,我们只要找到前面那些结尾比 3 小的子序列,然后把 3 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加一。

当然,可能形成很多种新的子序列,但是我们只要最长的,把最长子序列的长度作为 dp[5] 的值即可。

04.gif

for (int j=0;j < i; j++) {
    if (nums[j] < nums[i])
        dp[i] = Math.max(dp[i], dp[j] + 1);
}

这段代码的逻辑就可以算出 dp[5]。到这里,这道算法题我们就基本做完了。读者也许会问,我们刚才只是算了 dp[5] 呀,dp[4], dp[3] 这些怎么算呢?

类似数学归纳法,你已经可以通过 dp[0...4] 算出 dp[5] 了,那么任意 dp[i] 你肯定都可以算出来:

6.png

还有一个细节问题,就是 base case。dp 数组应该全部初始化为 1,因为子序列最少也要包含自己,所以长度最小为 1。下面我们看一下完整代码:

7.jpg

至此,这道题就解决了,时间复杂度 O(N^2)。总结一下动态规划的设计流程:

首先明确 dp 数组所存数据的含义。这步很重要,如果不得当或者不够清晰,会阻碍之后的步骤。

然后根据 dp 数组的定义,运用数学归纳法的思想,假设 dp[0...i−1] 都已知,想办法求出 dp[i],一旦这一步完成,整个题目基本就解决了。

但如果无法完成这一步,很可能就是 dp 数组的定义不够恰当,需要重新定义 dp 数组的含义;或者可能是 dp 数组存储的信息还不够,不足以推出下一步的答案,需要把 dp 数组扩大成二维数组甚至三维数组。

二、二分查找解法

这个解法的时间复杂度会将为 O(NlogN),但是说实话,正常人基本想不到这种解法(也许玩过某些纸牌游戏的人可以想出来)。所以如果大家了解一下就好,正常情况下能够给出动态规划解法就已经很不错了。

根据题目的意思,我都很难想象这个问题竟然能和二分查找扯上关系。其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关,甚至有一种排序方法就叫做 patience sorting(耐心排序)。

为了简单起见,后文跳过所有数学证明,通过一个简化的例子来理解一下思路。

首先,给你一排扑克牌,我们像遍历数组那样从左到右一张一张处理这些扑克牌,最终要把这些牌分成若干堆。

8.jpg

处理这些扑克牌要遵循以下规则:

只能把点数小的牌压到点数比它大的牌上。如果当前牌点数较大没有可以放置的堆,则新建一个堆,把这张牌放进去。如果当前牌有多个堆可供选择,则选择最左边的堆放置。

比如说上述的扑克牌最终会被分成这样 5 堆(我们认为 A 的值是最大的,而不是 1)。

9.jpg

为什么遇到多个可选择堆的时候要放到最左边的堆上呢?因为这样可以保证牌堆顶的牌有序(2, 4, 7, 8, Q),证明略。

10.jpg

按照上述规则执行,可以算出最长递增子序列,牌的堆数就是我们想求的最长递增子序列的长度,证明略。

11.jpg

我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个合适的牌堆顶来放吗,牌堆顶的牌不是有序吗,这就能用到二分查找了:用二分查找来搜索当前牌应放置的位置。

PS:旧文 二分查找算法详解 详细介绍了二分查找的细节及变体,这里就完美应用上了。如果没读过强烈建议阅读。

12.jpg

至此,二分查找的解法也讲解完毕。

这个解法确实很难想到。首先涉及数学证明,谁能想到按照这些规则执行,就能得到最长递增子序列呢?其次还有二分查找的运用,要是对二分查找的细节不清楚,给了思路也很难写对。

所以,这个方法作为思维拓展好了。但动态规划的设计方法应该完全理解:假设之前的答案已知,利用数学归纳的思想正确进行状态的推演转移,最终得到答案。

来源 | github

作者 | labuladong

取消 提交回答
全部回答(1)
相关问答

79

回答

小白用户ECS使用实践【持续连载中】

qilu 2014-06-18 15:37:00 73527浏览量 回答数 79

10

回答

【精品问答合集】Hbase热门问答

hbase小能手 2019-05-29 14:37:26 123041浏览量 回答数 10

37

回答

干货分享:DBA专家门诊一期:索引与sql优化问题汇总

xiaofanqie 2014-12-25 15:13:38 92954浏览量 回答数 37

38

回答

阿里官方Java代码规范标准《阿里巴巴Java开发手册》下载

管理贝贝 2017-02-10 15:14:36 79445浏览量 回答数 38

119

回答

OSS存储服务-客户端工具

newegg11 2012-05-17 15:37:18 300901浏览量 回答数 119

23

回答

【云服务器分享】网站访问速度快才是硬道理

dreamdoo 2012-10-15 10:15:02 86364浏览量 回答数 23

13

回答

【云服务器分享】如何节省网站流量

dreamdoo 2012-10-15 10:36:09 81433浏览量 回答数 13

62

回答

磁盘原地扩容功能4月22日正式上线

艳馨 2015-04-21 23:40:33 97128浏览量 回答数 62

23

回答

【精品问答合集】Redis热门问答

李博 bluemind 2019-05-29 16:36:15 130245浏览量 回答数 23

2

回答

区域选择帮助

fanyue88888 2012-12-07 15:54:30 205384浏览量 回答数 2
0
文章
103
问答
问答排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载