动态规划入门——在转移的时候使用二分法加速查找

今天我们一起来看一道非常经典的动态规划的问题，有多经典呢？我想了一下，大概是我这辈子做的最早的一道动态规划问题，以至于我现在都记得它的题面。

题面

这道题就是导弹拦截系统，说是某一个国家开发了一套导弹拦截系统，这个拦截系统可以拦截敌国打来的导弹。不同射程的导弹在弹射出去的时候的飞行高度都不同，这个拦截系统可以从低到高拦截飞来的导弹，但是它下一次拦截的高度必须大于等于上一次高度，只能升高不能降低。那么请问，假设我们检测到了所有敌国发射的导弹飞行的高度，请问我们最多可以拦截其中多少枚？

上面讲题意讲了这么多，其实用一句话就概括了，就是求一个序列当中最长不下降子序列的长度。也有题目反过来求最长不上升子序列，意思是一样的。

暴力解法

我们来看一个例子，假设敌国一共发来了8枚导弹，它们的飞行高度分别是：[65, 158, 170, 299, 300, 155, 207, 389]。

我们用眼睛看看还是蛮容易找出答案的，答案应该是[65, 158, 170, 299, 300, 389]一共6枚导弹，其中的155和207无法拦截。假设我们不知道这是一个动态规划算法，我们怎么想出解法呢？

还是老规矩，我们先从最简单的暴力方法开始思考。最暴力的方法就是枚举这n个数所有可能出现的状态，对于其中的每个元素而言，都有两种状态，一种是拿取，一种是不拿。那么对于一个n个元素的数组而言，显然一共会有个不同的可能。然后我们再依次判断每一种可能性是否合法，保留合法的长度最大的那一个。

当然我们也可以用搜索来做，我们可以在搜索的过程当中排除掉非法的组合，但在极端情况下，比如整个数组升序的时候，那么还是会枚举到所有的情况，那么整体的复杂度依然是。这显然是我们不能接受的。

那我们怎么来找到更好的解法呢？

感性的认识

我们观察和思考一下这个问题，我们会发现在这个问题当中，不同规模的解法应该都是一样的。如果某种方法可以解出长度为1000的序列，那么自然也可以解出长度为5的序列，反之也是一样。所以我们不由地可以想到，那我们从最简单的情况开始入手，能不能找到解法呢？

我们从长度为1的数组开始，显然答案是确定的，就是1.

如果长度是2呢？比如[65, 158]，那么我们需要判断一下第二个数能否跟在第一个数后面，也就是说第二个数是否大于等于第一个数，如果成立的话，那答案就是2，否则答案还是1，比如[65, 34]，最长的序列就只能是[65]或者[34]。

那如果是3个数呢？情况会复杂一点，我们可以反过来分析，如果答案是3，那么只有一种情况就是序列是递增的，如果答案是2，那么就有两种情况，一种是前面两个元素构成递增比如[20, 30, 10]，第二种情况是前面两个元素之中的一个和第三个数构成递增，比如[10, 5, 30]或者是[10, 5, 8]。也有可能答案是1，当序列是递减的时候。

表面上看我们什么也没有发现，并没有找出一个好的方案来解决问题，但是其实已经有一个很重要的结论摆在了我们面前——这个最长不下降的序列并不一定包含最后一个元素。

看起来这似乎是废话，答案当然可能不包含最后一个元素，因为如果最后一个元素非常小，它显然不可能组成很长的序列。但是反过来看，我们的结论会整个颠覆。既然答案并不一定以最后一个元素结尾，而序列必须有一个结尾，而目前我们没有结论证明某一个节点会不能作为结尾。所以我们自然地得出结论，所有位置都有可能是答案的结尾。

这个其实很好证明，我们来看下面这张图：

在这个序列当中，a1, a2到ai递增，从ai+1开始递减，并且，那么显然[a1. a2,...,ai]就是答案，也就是说ai就是答案的结尾。只要我们改变i的值，就可以让答案的结尾出现在不同的位置。所以理论上来说数组当中的每一个位置都可能是答案的结尾。

从这个结论出发我们可以得到另一个结论，既然所有位置都可能是最终答案的结尾，我们想要找到答案就需要遍历所有的结尾，也就是所有的位置。而且对于一个确定的位置而言，以它为结尾的最长不下降子序列必然也是确定的（可能有多种情况）。所以到这里，我们经过了一系列的推导，得出了一个结论，我们需要求解所有位置的答案，然后从其中选择整体上最优的那个。

这是一个很感性很直观的认识，但是离答案已经不远了，我们再加上一些理性的分析即可。

理性的分析

我们整理一下刚才的结论和思路，我们知道了我们要求解每一个位置的答案，然后从其中找到一个整体最优的。假设我们想要知道i位置结尾的答案，这其实意味着我们放弃了i位置后面所有的元素。我们考虑的序列只剩下了i以及i之前的部分。

我们来看下面这张图：

我们列举了一个长度等于5的数组的答案，我们遍历了所有的i，每一个i都对应num[:i]这个数组的答案。每一个i都可以看成是一个独立的问题，我们要做的就是求出每一个i对应的答案。

既然我们要求出每一个i的答案，那么我们能不能利用之前已经求出的结果来加速计算过程呢？推导到这里整个动态规划的思路已经非常清楚了。

我们假设，我们已经知道了所有小于等于i的答案，我们现在要求i+1的答案，应该怎么做呢？

很简单，我们遍历所有小于等于i的j，如果小于等于，那么说明可以跟在aj的后面，构成一个解。如果我们用dp数组来存储所有位置的答案，那么我们可以得到下面这个转移方程：

转移方程列出来之后就很简单了，我们从最小的i开始，利用前面的结果来计算每一个i对应的答案，然后从其中找出最大的作为整体的解即可。我们来看下代码，查看更多细节：

nums = [65, 158, 170, 299, 300, 155, 207, 389]

if __name__ == "__main__":
    n = len(nums)
    dp = [1 for _ in range(n)]
    
    for i in range(1, n):
        # 遍历i之前的所有已经得出答案的位置
        for j in range(i):
            # 如果i可以跟在j后面
            if nums[i] >= nums[j]:
                # 则尝试用j来更新i
                dp[i] = max(dp[i], dp[j] + 1)

    print(max(dp))

这段代码非常短，只有两重循环，结合之前的描述应该很容易理解。我们复杂度分析也很简单，从两重循环入手的话，我们显然是。我们也可以从状态数和决策数入手，我们每一个结尾的答案是状态，数量是n。对于每一个状态而言，它有可能跟在面面的每一个位置后面，所以潜在的决策数最坏也是n，所以整体的复杂度是。

虽然我们花费了很多笔墨，但是这个算法并不困难，的确是高中生竞赛的难度。但别着急，问题还没有结束，我们的下一个问题是，这个算法还有改进的空间吗?

进阶

既然这个问题问出来，显然答案是确定的。如果你在面试当中被面试官问还能有优化吗，你要是答没有，那可是会扣很多分的。面试官不是觉得你太鲁莽了就是觉得你情商捉鸡，所以如果面试的时候被问题，一定要回答有，至于怎么优化，那可以慢慢想，答不对都没问题，要是基调就定错了，可是很严重的。

动态规划问题的优化其实只有两种情况，要么从状态数入手，减少多余的状态数，要么从决策入手，快速找出正确的决策。比如之前介绍的单调优化就是后者，一般情况下来说状态数都是比较固定的，也是很难减少的，往往优化都要从决策上入手。这题也不例外，那么我们怎么来优化呢？

想要优化，眼前的信息是不够的，算法都不是凭空想出来的，往往是推导出来的。我们还需要更多的信息和结论才行，对于每一个要求的i+1位置而言，我们已经知道了它前面所有答案的情况。如果我们可以设计一个方法，快速地找到i+1究竟应该跟在哪个位置后面就好了。

这个方法我们干想是想不到的，必须要结合数据。我们用上面的样例来举例，画出所有位置最佳的转移决策：

好像也看不出什么眉目来，我们随意挑出一个元素来仔细查看，假设我们就挑选207。我们列举出207之前所有的位置的元素和答案，并且按照元素大小进行排序，可以得到这样的结果：

其中的155和158的长度都是2，显然我们可以去除掉158，只保留155。因为155 < 158，155能转移到的位置158一定也可以。我们把这个结论推广，也就是说对于长度相同的位置，我们只需要保留其中最小的那个。

我们观察上面这个序列，好像数字越大的长度也就越大，长度越大的数字也就越大，但真的是这样吗？我们试着更改一个值：

我们把158改成358，好像就不满足了，虽然358很大，但是它的答案很小。但是当我们根据上面的原则去重之后，我们剩下的序列还是递增的。这个只是巧合还是的确如此呢？

我们可以试着证明一下，假设存在反例。我们假设数组当中存在两个数x和y，这两个数同时存在于去重之后的答案数组当中。其中x < y，并且x的答案大于y。根据我们刚才排序的逻辑，那么x应该排在y的左侧。数组当中比x小的那些值必然也出现在x的左侧，那么必然存在一个位置的答案和y相等并且数值小于y，那么y必然会被去除，所以就和x和y同时存在矛盾了。

我们用下图来展示一下上面列举的反例。

也就是说对于我们经过处理之后得到的这个dp数组当中的元素必然是递增的，所以，其中每一个元素所在的位置其实就代表这个元素对应的长度。比如上图当中2排在数组当中的第二位，那么就说明2这个数字对应的答案是2。

我们更新dp数组的过程主要做了两件事，第一件事是让dp数组当中的元素尽量多，我们每次都会把最大的数插入dp的末尾。另外一件事情就是让dp数组当中的每个位置的元素尽量小。这样才可以为只有插入尽可能多的元素做准备，如果前面的数就特别大，那后面就没办法传入其他数了。

比如上图当中的3和9的答案都是3，但是显然3比9更好，因为3能够达到答案3，说明出现在3右侧的只要大于3的数至少可以获得4的长度。我们既可以理解成3对应的答案是3，也可以理解成答案3对应的最小满足的数是3，而不是9。

由于dp数组当中的元素有序，我们可以使用二分法来找到对应更新的位置，从而可以保证我们可以在logN的时间内找到最佳决策。那么整体的复杂度就变成了状态数是n，决策数是logN，最后的复杂度就是。

我们来看下代码：

from bisect import bisect_right

nums = [65, 158, 158, 299, 300, 155, 207, 389]

if __name__ == "__main__":
    n = len(nums)
    dp = [nums[0]]
    
    for i in range(1, n):
        if nums[i] >= dp[-1]:
            # 由于dp当中元素是递增的
            # 所以nums[i] > dp[-1]表示nums[i]是最大的
            dp.append(nums[i])
        else:
            # bisect_right是二分函数，找到dp当中大于nums[i]的位置
            pos = bisect_right(dp, nums[i])
            dp[pos] = nums[i]

    print(len(dp))

总结

到这里，这道题就讲解完了，整个题目的精髓在于我们维护了一个有序的数组，使得我们可以通过二分查找来找到每个状态的最佳决策。说来惭愧这道题我做过好几次，但是之前很多次都记不住解法，过段时间就会忘记，后来我才找到了诀窍。我们不能死记算法运行的原理，这样下次遇到了变体我们也做不出来。我们必须要理解这个优化出现的原因，推导的前因后果，这样我们才有能力推导其他的问题。

所以希望大家都能把这个推导的过程想明白，而不是只停留在我们怎么运用二分进行优化上。关于这道题还有其他的变种，举个例子，比如如果我们想要求出最少需要几套导弹系统能够拦截所有的导弹，应该怎么做呢？这个问题留给大家思考。我想如果能能够理解上面的做法，应该不难想出答案。