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

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

• 阶段性
• 无后效性
• 子问题重叠性

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

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

• 分而治之
• 想办法记录下中间的计算结果避免重复计算

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

• 我需要最少哪些数据，然后经过一些比较就能得出最终结果？
• 这些数据的求解是否可以用同样的方法分而治之？
• 过程中的运算结果如何保存复用？

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

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

• 线性DP
• 区间DP
• 树型DP
• 背包

线性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。
相关题目比如：

• 300. 最长上升子序列，裸题，但是要击败100%的话，需要单调队列优化。
• 354. 俄罗斯套娃信封问题，这道题还是hard。之前的最长上升序列是一维的，这道题是二维的上升序列，满足Ax<Bx且Ay<By，才可以构成上升序列。那么我们可以根据x进行排序，然后对y求解最长上升子序列。但是这里有个地方需要注意，因为x必须要严格升序，排序之后可能存在(1,1) (1,2) (1,3) (2,4)这样的序列，如果对y进行求解上升序列，会得到4，但是实际应该只是2。为了避免这个问题，在排序时，如果x相等，则y按照降序排列，就可以规避这个问题。
• 合唱队形，这道题是要求一个形如1 3 4 7 9 8 6 5 2这样的子序列。先上升再下降，最后求最长的长度。其实解决办法也很简单，先从左到右求出所有的最长上升序列asc[i]，再从右到左求出所有的最长上升序列reverseAcc[i]，最大值就是max(asc[i]+reverseAcc[i])。对算法要能够灵活运用。

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

LCS 最长公共子序列

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

• f[i][j] = f[i-1][j-1] + 1 ...... S[i]==T[j]
• f[i][j] = max(f[i-1][j], f[i][j-1]) ...... S[i]≠T[j]

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

• 1143. Longest Common Subsequence：这道题就是裸的LCS
• 583. Delete Operation for Two Strings：两个字符串要删除成一样的，所以先找出最长公共序列，然后剩下的都删了。
• 718. Maximum Length of Repeated Subarray：这道题其实本质上不是LCS，它是寻找最长子数组，而不是子序列（子数组要求连续）。需要搞清它们的区别。找子数组就更简单了，因为必须连续，所以f[i][j] = f[i-1][j-1]+1 : 0 ? S[i]==T[j]。通过倒序枚举能够把空间优化为O(N)。
• 1092. Shortest Common Supersequence：这道题是hard，实际上也不算很hard。其实就是找到最长公共子序列，然后，对于A字符串，把除了LCS以外的字符插入到对应的位置；对于B字符串也做同样的操作。这道题大家需要掌握一个新姿势，就是除了求最长公共子序列有多长，还要会打印最长公共子序列（follow up：打印所有可能的最长公共子序列）。同时，要把剩余的字符插入到对应的位置其实可以想办法把原字符串按照LCS切分成k+1段，比如对于字符串A abcxdef，其lcs为bde，那么我们可以把原字符串切成4段 a bcx d ef，同样对于B字符串，也能切成4段，然后对应插入构成新字符串即可，需要注意的就是，从第1段开始，第一个字符是lcs字符，所以只插一次。相关代码可以参考我的实现

线性递推

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

股票买卖问题

• 121. Best Time to Buy and Sell Stock：当前的最大收益只依赖于之前的最小买入价格。因此只需要一个变量保存截至目前的最低价即可，每次更新最大收益。
• 122. Best Time to Buy and Sell Stock II：由于可以进行多次交易，那么只要明天比今天价格高就有得赚，就可以进行交易。不需要去找波峰波谷，因为day2-day1+day3-day2 == day3-day1。当然，这里掌握怎么找波峰波谷的代码很重要，后面题目的优化会用到
• 123. Best Time to Buy and Sell Stock III：要求最多交易两次，而第二次交易必须建立在完成第一次交易的基础之上，因此对于每天来说，存在4种状态：第一次买、第一次卖、第二次买、第二次卖）。我们可以用f[i][0..=4]来表示这些状态：
  • 对于第一次买，f[i][1] = max(f[i-1][1], -prices[i])
  • 第一次卖，f[i][2] = max(f[i-1][2], f[i-1][1]+prices[i])
  • 第二次买，f[i][3] = max(f[i-1][3], f[i-1][2]-prices[i])
  • 第二次卖，f[i][4] = max(f[i-1][4], f[i-1][3]+prices[i])

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

 first_buy = max( first_buy,  -p[i] )
 first_sell = max(first_sell,  first_buy + p[i] )
 second_buy = max(second_buy,  -p[i] )
 second_sell = max(second_sell, second_buy + p[i] )

• 188. Best Time to Buy and Sell Stock IV：这道题更进一步，要求最多不超过k次交易。这道题有几个小优化点：
  • 由于一次交易需要2天，n天最后进行n/2次交易，因此如果k>=n/2，那么这道题就简化为不限交易次数的122. Best Time to Buy and Sell Stock II
  • 对于 1 3 4 6 7 7 8这样的上升序列，交易3次和一头一尾交易一次的结果是一样的，因此可以只保留1 8,；同理，对于8 7 7 5 4 4 2 1这样的连续下降序列，由于价格连续下降，中间进行交易肯定亏，因此在最低点再买入肯定比高点买入划算，可以只保留8 1（保留8是因为它是前一个的上升序列的高点）。这种方式能够在绝大部分情况大大减少数据规模，配合第一个小优化，很容易把题目简化成不限交易次数的122. Best Time to Buy and Sell Stock II

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

for j in 0..prices.len() {
  let price = prices[j];
  f[0] = max(f[0], -price);
  f[1] = max(f[1], f[0]+price);
  for i in 1..k { // 这里还有个优化，因为只枚举到第j天，因此最多能进行j/2+1次交易，这里可以只枚举到min(k, j/2+1)
    f[i*2] = max(f[i*2], f[i*2-1]-p[j]);
    f[i*2+1] = max(f[i*2+1], f[i*2]+p[j]);
  }
}

打家劫舍

• 198. House Robber：其实就是在一个数组中取数，数与数之间至少隔一个，问最大能取到多少。由于第i个数能不能取依赖于前一个数是否被取过，因此用f[i]表示取第i个数能得到的最大值，用g[i]表示不取第i个数能得到的最大值。f[i] = g[i-1]+a[i], g[i] = max(f[i-1], g[i-1])。然后发现，由于只和前一项有关，因此可以只用两个变量来保存。f = g+a[i]，g = max(g, f)。
• 213. House Robber II：同样的规则，只是把数组变成了环，意味收尾两个数也相邻了。怎么处理环这个约束呢？其实就是，只要取了第一个就不能取最后一个，或者取了最后一个就不能取第一个。要解决这个问题一个简单的办法就是，直接把最后一个元素删了，然后进行一次DP，得到结果A。然后把最后一个元素加回去再把第一个元素删了，进行一次DP，得到结果B。这样能够保证不会同时取到收尾元素。最后比较AB，取较大值即可。
• 337. House Robber III：这道题把数组变成了二叉树，要求父节点和子节点不能同时取。虽然是在树上DP，但其实也很简单。设计一个get(root) -> (i32, i32)方法，此方法返回两个值，一个是取根节点所能达到的最大值，一个是不取根节点能达到的最大值。伪代码如下：

fn get(root) -> (i32, i32) {
  if root.is_none() {
    return (0,0);
  }
  let (lch_with_root, lch_without_root) = get(root.lch);
  let (rch_with_root, rch_without_root) = get(root.rch);
  (
    root.val+lch_without_root+rch_without_root,
    max(lch_with_root, lch_without_root) + max(rch_with_root, rch_without_root),
  )
}

粉刷房子

• 256. 粉刷房子：因为相邻房子不能颜色一样，因此当前房子刷什么颜色还依赖于它前一个房子刷什么颜色。因此用f[i][j]表示前i个房子，且第i个房子刷颜色j能得到的最小花费。那么f[i][j] = min(f[i-1][k])+cost[i][j]，其中k!=j。也就是从前i-1个房子，且第i-1个房子刷颜色k，转移过来。由于相邻颜色不能一样，因此不能从f[i-1][j]转移，即k!=j。由于f[i]只和f[i-1]有关，因此可以用01滚动来优化一维空间。而且对于这道题，只有三种颜色，实际上完全可以用6个变量pre_red, pre_blue, pre_green, red, blue, green来表示。
• 265. 粉刷房子 II：同上一题，这道题颜色不固定，因此使用f[2][0..k]来分别表示k种颜色的状态。f[i][j] = min(f[1-i][k])+cost[i][j]

小结

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