Question

算法题套路总结（三）——动态规划

Answer 1

前两篇我总结了链表和二分查找题目的一些套路，这篇文章来讲讲动态规划。动态规划从我高中开始参加NOIP起就一直是令我比较害怕的题型，除了能一眼看出来转移方程的题目，大部分动态规划都不太会做。加上后来ACM更为令人头秃的动态规划，很多题解看了之后，我根本就不相信自己能够想出来这种解法，看着大佬们谈笑间还加一些常数优化，一度怀疑自己的智商。以前一直觉得动态规划是给大佬准备的，所以刻意地没有去攻克它，主要也是没有信心。但是后来慢慢的，我再做LC的时候，发现很多DP的题目我自己慢慢能够推出转移方程了，而且似乎也没那么难。我一直在思考，到底是我变强了，还是因为LC的题目相比ACM或者NOI太简单了。其实主要还是后者，但是同时我也发现，动态规划其实是有套路的，我以前方法不对，总结太少。
主要就是，站在出题人的角度，他几乎不太可能完全凭空想出一个新的DP模型，因为动态规划毕竟要满足：

因此，能够利用DP来解决的问题实际上是有限的，大部分题目都是针对现有的模型的一些变种，改改题目描述，或者加点限制条件。所以要想攻克DP题目，最根本的就是要充分理解几个常见的DP模型。而要充分理解常见经典DP模型，就需要通过大量的做题和总结，而且二者不可偏废。通过做题进行思考和量的积累，通过总结加深理解和融会贯通进而完成质的提升。

动态规划是求解一个最优化问题，而最核心的思想就是：

解一道DP题目，先问自己几个问题：

当然以上内容看起来比较抽象，虽然它深刻地揭露了动态规划的本质，但是如果临场要去想明白这些问题，还是有些难度。如果只是针对比赛和面试，就像前面说的，DP题型是有限的。只要刷的题目足够多，总结出几个经典模型，剩下的都是些变种+优化而已。

一般来说，动态规划可以分成4个大类:

线性DP就是阶段非常线性直观的模型，比如：最长（上升|下降）序列，最长公共子序列(LCS)等，也有一些简单的递推，甚至都算不上是 经典模型 。

最长上升序列是一个非常经典的线性模型。说它是个模型，是因为它是一类题的代表，很多题目都只是换个说法，或者要求在这基础上进一步优化而已。最长上升序列最基础的转移方程就是 f[i] = max{f[j]}+1 (a[i] > a[j]) , f[i] 表示一定要以 a[i] 结尾的序列，最长长度是多少。很显然就是在前面找到一个最大的 f[j] 同时满足 a[j]<a[i] 。因此是 N^2 的时间复杂度和N的空间复杂度。这种方法是最朴素直观的，一定要理解。它非常简单，因此很少有题目直接能够这么做。大部分相关题目需要进一步优化，也就是有名的单调队列优化，能够把复杂度优化到nlogn。

说单调队列优化之前必须明白一个贪心策略。因为要求的是最长上升序列，那么很显然长度为k的上升序列的最大值（最后一个数）越小越好，这样后面的数才有更大的概率比它大。如果我们记录下来不同长度的上升序列的最后一个数能达到的最小值，那么对于后续每个数t，它要么能放到某个长度为y的序列之后，组成长度为y+1的上升序列，要么放到某个长度为x的序列后面，把长度为x+1的序列的最大值替换成t。同时我们可以发现，如果x<y，那么长度为x序列的最后一个数一定比长度为y的序列最后一个数小。因此这个上升序列我们可以用一个数组来维护（所谓的单调队列），数组下标就代表序列长度。 opt[i]=t 表示长度为i的上升序列最后一个数最小是t。那么当我们在面对后续某个数x时，可以对单调队列opt进行二分，把它插到对应的位置。因此总体复杂度就是NlogN。
相关题目比如：

但是你可以发现，其实这个题型其实变种很有限，吃透了也就那么回事。所以一定要总结。

最长公共子序列也是线性DP中的一种比较常见的模型。说它是一种“模型”其实有点拔高了，其实它就是一类比较常见的题目。很多题目都是在LCS的基础上进行简单的扩展，或者仅仅就是换一个说法而已。
求两个数组的最长公共子序列，最直观地做法就是：设f[i][j]表示S[..i]和T[..j]的最长公共子序列，则有:

这个转移方程也非常好理解，时间复杂度是 N^2 ，空间复杂度也是 N^2 。不过仔细观察你可以发现，当我们计算第i行时只与i-1和i行有关。因此我们可以利用01滚动来优化空间复杂度为2N。
相关题目：

线性DP除了上述的两种常见题型，还有很多别的类型，包括背包。我们要努力去尝试理解这些题目的异同，它们的转移方程，以及思路，可能的变化，这样才能更好的应对未知的题目。以下是一些我总结的题型：

最终结果就是max(0, f[n][2]+f[n][4])。
不过实际上你可以发现，由于各个状态只和前一维有关，且只能由固定的一个状态转移过来，因此我们可以省掉一维，只用4个变量来存储：

剩下的，同123题类似，由于最多进行k次交易，那么一天就有2k个状态：第1次买/卖……第k次买/卖，结合123题的优化，我们只需要2k个变量就能存储这些状态。因此设f[i×2]为第i次买入的最优值，f[i×2+1]为第i次卖出的最优值：

以上都是对一些常见的线性DP的一些小结，实际上线性DP还有一个重要的题型就是背包。关于背包，有很多相关的讲解，我这里就不多说了，推荐大家看看 背包九讲 。下一章依然是DP专题，我讲总结一些区间DP的题型。大部分区间DP都是hard级的，对于希望提高自己水平的人来说，需要投入更多精力去理解。