今天是算法与数据结构专题的17篇文章，也是动态规划专题的第6篇。
今天我们一起来看一道非常经典的动态规划的问题，有多经典呢？我想了一下，大概是我这辈子做的最早的一道动态规划问题，以至于我现在都记得它的题面。
题面
这道题就是导弹拦截系统，说是某一个国家开发了一套导弹拦截系统，这个拦截系统可以拦截敌国打来的导弹。不同射程的导弹在弹射出去的时候的飞行高度都不同，这个拦截系统可以从低到高拦截飞来的导弹，但是它下一次拦截的高度必须大于等于上一次高度，只能升高不能降低。那么请问，假设我们检测到了所有敌国发射的导弹飞行的高度，请问我们最多可以拦截其中多少枚？
上面讲题意讲了这么多，其实用一句话就概括了，就是求一个序列当中最长不下降子序列的长度。也有题目反过来求最长不上升子序列，意思是一样的。
暴力解法
我们来看一个例子，假设敌国一共发来了8枚导弹，它们的飞行高度分别是：[65, 158, 170, 299, 300, 155, 207, 389]。
我们用眼睛看看还是蛮容易找出答案的，答案应该是[65, 158, 170, 299, 300, 389]一共6枚导弹，其中的155和207无法拦截。假设我们不知道这是一个动态规划算法，我们怎么想出解法呢？
还是老规矩，我们先从最简单的暴力方法开始思考。最暴力的方法就是枚举这n个数所有可能出现的状态，对于其中的每个元素而言，都有两种状态，一种是拿取，一种是不拿。那么对于一个n个元素的数组而言，显然一共会有 2^n 个不同的可能。然后我们再依次判断每一种可能性是否合法，保留合法的长度最大的那一个。
当然我们也可以用搜索来做，我们可以在搜索的过程当中排除掉非法的组合，但在极端情况下，比如整个数组升序的时候，那么还是会枚举到所有的情况，那么整体的复杂度依然是 2^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开始递减，并且 ai 1 < a1，那么显然[a1. a2,...,ai]就是答案，也就是说ai就是答案的结尾。只要我们改变i的值，就可以让答案的结尾出现在不同的位置。所以理论上来说数组当中的每一个位置都可能是答案的结尾。
从这个结论出发我们可以得到另一个结论，既然所有位置都可能是最终答案的结尾，我们想要找到答案就需要遍历所有的结尾，也就是所有的位置。而且对于一个确定的位置而言，以它为结尾的最长不下降子序列必然也是确定的（可能有多种情况）。所以到这里，我们经过了一系列的推导，得出了一个结论，我们需要求解所有位置的答案，然后从其中选择整体上最优的那个。
这是一个很感性很直观的认识，但是离答案已经不远了，我们再加上一些理性的分析即可。
理性的分析
我们整理一下刚才的结论和思路，我们知道了我们要求解每一个位置的答案，然后从其中找到一个整体最优的。假设我们想要知道i位置结尾的答案，这其实意味着我们放弃了i位置后面所有的元素。我们考虑的序列只剩下了i以及i之前的部分。
我们来看下面这张图：
我们列举了一个长度等于5的数组的答案，我们遍历了所有的i，每一个i都对应num[:i]这个数组的答案。每一个i都可以看成是一个独立的问题，我们要做的就是求出每一个i对应的答案。
既然我们要求出每一个i的答案，那么我们能不能利用之前已经求出的结果来加速计算过程呢？推导到这里整个动态规划的思路已经非常清楚了。
我们假设，我们已经知道了所有小于等于i的答案，我们现在要求i 1的答案，应该怎么做呢？
很简单，我们遍历所有小于等于i的j，如果 aj 小于等于 ai 1，那么说明 ai 1 可以跟在aj的后面，构成一个解。如果我们用dp数组来存储所有位置的答案，那么我们可以得到下面这个转移方程：
转移方程列出来之后就很简单了，我们从最小的i开始，利用前面的结果来计算每一个i对应的答案，然后从其中找出最大的作为整体的解即可。我们来看下代码，查看更多细节：
