夜深人静写算法（2）：动态规划（上）

（点击上方公众号，可快速关注）

来源： 英雄哪里出来

cppblog.com/menjitianya/archive/2015/10/23/212084.html

如有好文章投稿，请点击 → 这里了解详情

目录

一、动态规划初探

1、递推

2、记忆化搜索

3、状态和状态转移

4、最优化原理和最优子结构

5、决策和无后效性

二、动态规划的经典模型

1、线性模型

2、区间模型

3、背包模型

4、状态压缩模型

5、树状模型

三、动态规划的常用状态转移方程

1、1D/1D

2、2D/0D

3、2D/1D

4、2D/2D

四、动态规划和数据结构结合的常用优化

1、滚动数组

2、最长单调子序列的二分优化

3、矩阵优化

4、斜率优化

5、树状数组优化

6、线段树优化

7、其他优化

五、动态规划题集整理

一、动态规划初探

1、递推

暂且先不说动态规划是怎么样一个算法，由最简单的递推问题说起应该是最恰当不过得了。因为一来，递推的思想非常浅显，从初中开始就已经有涉及，等差数列 f[i] = f[i-1] + d（ i > 0， d为公差，f[0]为初项）就是最简单的递推公式之一；二来，递推作为动态规划的基本方法，对理解动态规划起着至关重要的作用。理论的开始总是枯燥的，所以让读者提前进入思考是最能引起读者兴趣的利器，于是【例题1】应运而生。

【例题1】在一个3 X N的长方形方格中，铺满1X2的骨牌（骨牌个数不限制），给定N，求方案数（图一 -1-1为N=2的所有方案），所以N=2时方案数为3。

图一 -1-1

这是一个经典的递推问题，如果觉得无从下手，我们可以来看一个更加简单的问题，把问题中的“3”变成“2”（即在一个2XN的长方形方格中铺满1X2的骨牌的方案）。这样问题就简单很多了，我们用f[i]表示2Xi的方格铺满骨牌的方案数，那么考虑第i列，要么竖着放置一个骨牌；要么连同i-1列，横着放置两个骨牌，如图2所示。由于骨牌的长度为1X2，所以在第i列放置的骨牌无法影响到第i-2列。很显然，图一 -1-2中两块黑色的部分分别表示f[i-1]和f[i-2]，所以可以得到递推式f[i] = f[i-1] + f[i-2] (i >= 2)，并且边界条件f[0] = f[1] = 1。

图一 -1-2

再回头来看3 X N的情况，首先可以明确当N等于奇数的时候，方案数一定为0。所以如果用f[i] (i 为偶数) 表示3Xi的方格铺满骨牌的方案数，f[i]的方案数不可能由f[i-1]递推而来。那么我们猜想f[i]和f[i-2]一定是有关系的，如图一 -1-3所示，我们把第i列和第i-1列用1X2的骨牌填满后，轻易转化成了f[i-2]的问题，那是不是代表f[i] = 3*f[i-2]呢？

图一 -1-3

仔细想想才发现不对，原因是我们少考虑了图一 -1-4的情况，这些情况用图一 -1-3的情况无法表示，再填充完黑色区域后，发现和f[i-4]也有关系，但是还是漏掉了一些情况。

图一 -1-4

上面的问题说明我们在设计状态（状态在动态规划中是个很重要的概念，在本章的第4小节会进行介绍总结）的时候的思维定式，当一维的状态已经无法满足我们的需求时，我们可以试着增加一维，用二维来表示状态，用f[i][j]表示(3 X i) + j个多余块的摆放方案数，如图一 -1-5所示：

图一 -1-5

转化成二维后，我们可以轻易写出三种情况的递推式，具体推导方法见图一 -1-6。

f[i][0] = f[i-2][0] + f[i-1][1] + f[i-2][2]

f[i][1] = f[i-1][2]

f[i][2] = f[i][0] + f[i-1][1]

边界条件 f[0][0] = f[1][1] = f[0][2] = 1

图一 -1-6

如果N不是很大的情况，到这一步，我们的问题已经完美解决了，其实并不需要求它的通项公式，因为我们是程序猿，一个for循环就能搞定了 <*_*>，接下来的求解就全仰仗于计算机来完成了。

【例题2】对一个“01”串进行一次μ变换被定义为：将其中的”0″变成”10″，”1″变成”01″，初始串为”1″，求经过N(N <= 1000)次μ变换后的串中有多少对”00″（有没有人会纠结会不会出现”000″的情况？这个请放心，由于问题的特殊性，不会出现”000″的情况）。图一 -1-7表示经过小于4次变换时串的情况。

图一 -1-7

如果纯模拟的话，每次μ变换串的长度都会加倍，所以时间和空间复杂度都是O(2^n)，对于n为1000的情况，完全不可能计算出来。仔细观察这个树形结构，可以发现要出现”00″，一定是”10″和”01″相邻产生的。为了将问题简化，我们不妨设A = “10″, B = “01″，构造出的树形递推图如图一 -1-8所示，如果要出现”00″，一定是AB（”1001″）。

令FA[i]为A经过i次μ变换后”00″的数量，FA[0] = 0;FB[i]为B经过i次μ变换后”00″的数量，FB[0] = 0。

从图中观察得出，以A为根的树，它的左子树的最右端点一定是B，也就是说无论经过多少次变换，两棵子树的交界处都不可能产生AB，所以FA[i] = FB[i-1] + FA[i-1]（直接累加两棵子树的”00″的数量）；而以B为根的树，它的左子树的右端点一定是A，而右子树的左端点呈BABABA…交替排布，所以隔代产生一次AB，于是FB[i] = FA[i-1] + FB[i-1] + (i mod 2) 。最后要求的答案就是FB[N-1]，递推求解。

图一 -1-8

2、记忆化搜索

递推说白了就是在知道前i-1项的值的前提下，计算第i项的值，而记忆化搜索则是另外一种思路。它是直接计算第i项，需要用到第 j 项的值( j < i)时去查表，如果表里已经有第 j 项的话，则直接取出来用，否则递归计算第 j 项，并且在计算完毕后把值记录在表中。记忆化搜索在求解多维的情况下比递推更加方便，【例题3】是我遇到的第一个记忆化搜索的问题，记忆犹新。

【例题3】这个问题直接给出了一段求函数w(a, b, c)的伪代码：

function w(a, b, c):

if a <=0 or b <=0 or c <=0, then returns:1

if a >20or b >20or c >20, then returns: w(20,20,20)

if a < b and b < c, then returns: w(a, b, c-1)+ w(a, b-1, c-1)- w(a, b-1, c)

otherwise it returns: w(a-1, b, c)+ w(a-1, b-1, c)+ w(a-1, b, c-1)

要求给定a, b, c，求w(a, b, c)的值。

乍看下只要将伪代码翻译成实际代码，然后直接对于给定的a, b, c，调用函数w(a, b, c)就能得到值了。但是只要稍加分析就能看出这个函数的时间复杂度是指数级的（尽管这个三元组的最大元素只有20，这是个陷阱）。对于任意一个三元组(a, b, c)，w(a, b, c)可能被计算多次，而对于固定的(a, b, c)，w(a, b, c)其实是个固定的值，没必要多次计算，所以只要将计算过的值保存在f[a][b][c]中，整个计算就只有一次了，总的时间复杂度就是O(n^3)，这个问题的n只有20。

3、状态和状态转移

在介绍递推和记忆化搜索的时候，都会涉及到一个词—状态，它表示了解决某一问题的中间结果，这是一个比较抽象的概念，例如【例题1】中的f[i][j]，【例题2】中的FA[i]、FB[i]，【例题3】中的f[a][b][c]，无论是递推还是记忆化搜索，首先要设计出合适的状态，然后通过状态的特征建立状态转移方程（f[i] = f[i-1] + f[i-2] 就是一个简单的状态转移方程）。

4、最优化原理和最优子结构

在介如果问题的最优解包含的子问题的解也是最优的，就称该问题具有最有子结构，即满足最优化原理。这里我尽力减少理论化的概念，而改用一个简单的例题来加深对这句话的理解。

【例题4】给定一个长度为n(1 <= n <= 1000)的整数序列a[i]，求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列)，满足如下条件：

1. 该序列单调递增；

2. 在所有满足条件1的序列中长度是最长的；

这个问题是经典的动态规划问题，被称为最长单调子序列。

我们假设现在没有任何动态规划的基础，那么看到这个问题首先想到的是什么？

我想到的是万金油算法—枚举（DFS），即枚举a[i]这个元素取或不取，所有取的元素组成一个合法的子序列，枚举的时候需要满足单调递增这个限制，那么对于一个n个元素的序列，最坏时间复杂度自然就是O(2n)，n等于30就已经很变态了更别说是1000。但是方向是对的，动态规划求解之前先试想一下搜索的正确性，这里搜索的正确性是很显然的，因为已经枚举了所有情况，总有一种情况是我们要求的解。我们尝试将搜索的算法进行一些改进，假设第i个数取的情况下已经搜索出的最大长度记录在数组d中，即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的长度，那么如果下次搜索得到的序列长度小于等于d[i]，就不必往下搜索了（因为即便继续往后枚举，能够得到的解必定不会比之前更长）；反之，则需要更新d[i]的值。如图一-4-1，红色路径表示第一次搜索得到的一个最长子序列1、2、3、5，蓝色路径表示第二次搜索，当枚举第3个元素取的情况时，发现以第3个数结尾的最长长度d[3] = 3，比本次枚举的长度要大（本次枚举的长度为2），所以放弃往下枚举，大大减少了搜索的状态空间。

图一-4-1

这时候，我们其实已经不经意间设计好了状态，就是上文中提到的那个d[i]数组，它表示的是以a[i]结尾的最长单调子序列的长度，那么对于任意的i，d[i] 一定等于 d[j] + 1 ( j < i )，而且还得满足 a[j] < a[i]。因为这里的d[i]表示的是最长长度，所以d[i]的表达式可以更加明确，即：

d[i] = max{ d[j] | j < i && a[j] < a[i] } + 1

这个表达式很好的阐释了最优化原理，其中d[j]作为d[i]的子问题，d[i]最长（优）当且仅当d[j]最长（优）。当然，这个方程就是这个问题的状态转移方程。状态总数量O(n), 每次转移需要用到前i项的结果，平摊下来也是O(n)的,所以该问题的时间复杂度是O(n^2)，然而它并不是求解这类问题的最优解，下文会提到最长单调子序列的O(nlogn)的优化算法。

5、决策和无后效性

一个状态演变到另一个状态，往往是通过“决策”来进行的。有了“决策”，就会有状态转移。而无后效性，就是一旦某个状态确定后，它之前的状态无法对它之后的状态产生“效应”（影响）。

【例题5】老王想在未来的n年内每年都持有电脑，m(y, z)表示第y年到第z年的电脑维护费用，其中y的范围为[1, n]，z的范围为[y, n]，c表示买一台新的电脑的固定费用。 给定矩阵m，固定费用c，求在未来n年都有电脑的最少花费。

考虑第 i 年是否要换电脑，换和不换是不一样的决策，那么我们定义一个二元组(a, b)，其中 a < b，它表示了第a年和第b年都要换电脑（第a年和第b年之间不再换电脑），如果假设我们到第a年为止换电脑的最优方案已经确定，那么第a年以前如何换电脑的一些列步骤变得不再重要，因为它并不会影响第b年的情况，这就是无后效性。

更加具体得，令d[i]表示在第i年买了一台电脑的最小花费(由于这台电脑能用多久不确定，所以第i年的维护费用暂时不计在这里面)，如果上一次更换电脑的时间在第j年，那么第j年更换电脑到第i年之前的总开销就是c + m(j, i-1)，于是有状态转移方程：

d[i] = min{ d[j] + m(j, i-1) | 1 <= j < i }+ c

这里的d[i]并不是最后问题的解，因为它漏算了第i年到第n年的维护费用，所以最后问题的答案：

ans = min{ d[i] + m(i, n) | 1 <= i < n }

我们发现两个方程看起来很类似，其实是可以合并的，我们可以假设第n+1年必须换电脑，并且第n+1年换电脑的费用为0，那么整个阶段的状态转移方程就是：

d[i] = min{ d[j] + m(j, i-1) | 1 <= j < i } + w(i) 其中w(i) = (i==n+1)?0:c;

d[n+1]就是我们需要求的最小费用了。

二、动态规划的经典模型

1、线性模型

线性模型的是动态规划中最常用的模型，上文讲到的最长单调子序列就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。【例题6】是一个经典的面试题，我们将它作为线性模型的敲门砖。

【例题6】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

图二-1-1

每次过桥的时候最多两个人，如果桥这边还有人，那么还得回来一个人（送手电筒），也就是说N个人过桥的次数为2*N-3（倒推，当桥这边只剩两个人时只需要一次，三个人的情况为来回一次后加上两个人的情况…）。有一个人需要来回跑，将手电筒送回来（也许不是同一个人，realy？！）这个回来的时间是没办法省去的，并且回来的次数也是确定的，为N-2，如果是我，我会选择让跑的最快的人来干这件事情，但是我错了…如果总是跑得最快的人跑回来的话，那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了，花费的总时间：

T = minPTime * (N-2) + (totalSum-minPTime)

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19，但是实际答案应该是17。

具体步骤是这样的：

第一步：1和2过去，花费时间2，然后1回来（花费时间1）；

第二歩：3和4过去，花费时间10，然后2回来（花费时间2）；

第三部：1和2过去，花费时间2，总耗时17。

所以之前的贪心想法是不对的。

我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以opt[i] = opt[i-1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)

如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2] (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题)

所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] }

2、区间模型

区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。

【例题7】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。

典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，在X两边各添加一个字符’a'后，aXa仍然是一个回文串，我们用d[i][j]来表示A[i...j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：

1、在A[j]后面添加一个字符A[i]；

2、在A[i]前面添加一个字符A[j]；

根据两种决策列出状态转移方程为：

d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; (每次状态转移，区间长度增加1)

空间复杂度O(n^2)，时间复杂度O(n^2)， 下文会提到将空间复杂度降为O(n)的优化算法。

3、背包模型

背包问题是动态规划中一个最典型的问题之一。由于网上有非常详尽的背包讲解，这里只将常用部分抽出来，具体推导过程详见《背包九讲》。

a.0/1背包

有N种物品（每种物品1件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。决策为第i个物品在前i-1个物品放置完毕后，是选择放还是不放，状态转移方程为：

f[i][v] = max{ f[i-1][v], f[i-1][v - Ci] +Wi }

时间复杂度O(VN)，空间复杂度O(VN) （空间复杂度可利用滚动数组进行优化达到O(V)，下文会介绍滚动数组优化）。

b.完全背包

有N种物品（每种物品无限件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。

f[i][v] = max{ f[i-1][v - kCi] + kWi | 0 <= k <= v/Ci} (当k的取值为0,1时，这就是01背包的状态转移方程）

时间复杂度O( VNsum{V/Ci} )，空间复杂度在用滚动数组优化后可以达到O( V )。

进行优化后（此处省略500字），状态转移方程变成：

f[i][v] = max{ f[i-1][v], f[i][v - Ci] +Wi }

时间复杂度降为O(VN)。

c.多重背包

有N种物品（每种物品Mi件）和一个容量为V的背包。放入第i种物品耗费的空间是Ci，得到

的价值是Wi。求解将哪些物品装入背包可使价值总和最大。 f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。

f[i][v] = max{ f[i-1][v - kCi] + kWi | 0 <= k <= Mi }

时间复杂度O( Vsum(Mi) )，空间复杂度仍然可以用滚动数组优化后可以达到O( V )。

优化：采用二进制拆分物品，将Mi个物品拆分成容量为1、2、4、8、… 2^k、Mi-( 2^(k+1) – 1 ) 个对应价值为Wi、2Wi、4Wi、8Wi、…、2^kWi、（Mi-( 2^(k+1) – 1 )）Wi的物品，然后采用01背包求解。这样做的时间复杂度降为O(Vsum(logMi) )。

【例题8】一群强盗想要抢劫银行，总共N(N <= 100)个银行，第i个银行的资金为Bi亿，抢劫该银行被抓概率Pi，问在被抓概率小于p的情况下能够抢劫的最大资金是多少？

p表示的是强盗在抢银行时至少有一次被抓概率的上限，那么选择一些银行，并且计算抢劫这些银行都不被抓的的概率pc，则需要满足1 – pc < p。这里的pc是所有选出来的银行的抢劫时不被抓概率（即1 – Pi）的乘积，于是我们用资金作为背包物品的容量，概率作为背包物品的价值，求01背包。状态转移方程为：

f[j] = max{ f[j], f[j - pack[i].B] * (1-pack[i].p) }

最后得到的f[i]表示的是抢劫到 i 亿资金的最大不被抓概率。令所有银行资金总和为V，那么从V-0进行枚举，第一个满足1 – f[i] < p的i就是我们所要求的被抓概率小于p的最大资金。

4、状态压缩模型

状态压缩的动态规划，一般处理的是数据规模较小的问题，将状态压缩成k进制的整数，k取2时最为常见。

【例题9】对于一条n(n <= 11)个点的哈密尔顿路径C1C2…CN（经过每个点一次的路径）的值由三部分组成：

1、每个顶点的权值Vi的和

2、对于路径上相邻的任意两个顶点CiCi+1，累加权值乘积 Vi*Vi+1

3、对于相邻的三个顶点CiCi+1Ci+2，如果Ci和Ci+2之间有边，那么累加权值三乘积 Vi*Vi+1*Vi+2

求值最大的哈密尔顿路径的权值 和 这样的路径的个数。

枚举所有路径，判断找出值最大的，复杂度为O(n！)，取缔！

由于点数较少，采用二进制表示状态，用d[i][j][k]表示某条哈密尔顿路径的最大权值，其中i是一个二进制整数，它的第t位为1表示t这个顶点在这条哈密尔顿路径上，为0表示不在路径上。j和k分别为路径的最后两个顶点。那么图二-4-1表示的状态就是：

d[(11101111)2][7][1]

图二-4-1

明确了状态表示，那么我们假设02356这5个点中和7直接相连的是i，于是就转化成了子问题…->j -> i -> 7，我们可以枚举i = 0， 2， 3， 5， 6。

直接给出状态转移方程：

d[i][j][k] = max{ d[i ^ (1<<k)][t][j] + w(t, j, k) | (i & (1<<t)) != 0 }

这里用到了几个位运算:i ^ (1<<k)表示将i的二进制的第k位从1变成0，i & (1<<t)则为判断i的二进制表示的第t位是否为1，即该路径中是否存在t这个点。这个状态转移的实质就是将原本的 …->j -> k 转化成更加小规模的去掉k点后的子问题 … -> t -> j 求解。而w(t, j, k)则表示 t->j->k这条子路径上产生的权值和，这个可以由定义在O(1)的时间计算出来。

d[ (1<<j) | (1<<k) ][j][k] 为所有的两个点的路径的最大值，即最小的子问题。这个问题的状态并非线性的，所以用记忆化搜索来求解状态的值会事半功倍。

【例题10】

方块A

方块B

利用以上两种积木（任意数量，可进行旋转和翻转），拼出一个m*n( 1<= m <= 9, 1 <= n <= 9 )的矩形，问这样的方式有多少种。如m = 2, n = 3的情况

，有以下5种拼接方式：

图二-4-2

经典问题，2进制状态压缩。有固定套路，就不纠结是怎么想出来的了， 反正第一次看到这种问题我是想不出来，你呢？但是照例还是得引导一下。

如果问题不是求放满的方案数，而是求前M-1行放满，并且第M行的奇数格放上骨牌而偶数格不放 或者 第M行有一个格子留空 或者 第M行的首尾两个格子留空，求方案数（这是三个问题，分别对应图二-4-3的三个图）。这样的问题可以出一箩筐了，因为第M行的情况总共有2^n，按照这个思路下去，我们发现第i (1 <= i <= m)行的状态顶多也就2^n种，这里的状态可以用一个二进制整数来表示，对于第i行，如果这一行的第j个格子被骨牌填充则这个二进制整数的第j位为1，否则为0。

图二-4-3中的三个图的第M行状态可以分别表示为(101010) 2、(110111) 2、(011110) 2，那么如果我们已知第i行的状态k对应的方案数，并且状态k放置几个骨牌后能够将i+1行的状态变成k’，那么第i+1行的k’这个状态的方案数必然包含了第i行的状态k的方案数，这个放置骨牌的过程就是状态转移。

图二-4-3

用一个二维数组DP[i][j] 表示第i行的状态为j的骨牌放置方案数(其中 1<=i<=m, 0 <= j < 2n)，为了将问题简化，我们虚拟出一个第0行，则有DP[0][j] = (j == 2n-1) ? 1 : 0；这个就是我们的初始状态，它的含义是这样的，因为第0行是我们虚拟出来的，所以第0行只有完全放满的时候才有意义，也就是第0行全部放满（状态的二进制表示全为1，即十进制表示的2n-1）的方案数为1，其它情况均为0。

那么如何进行状态转移呢？假设第3行的某个状态(101000)2的方案数DP[3][(101000)2 ] = 5，如图二-4-4所示：

图二-4-4

我们需要做的就是通过各种方法将第3行填满，从而得到一系列第4行可能的状态集合S，并且对于每一个在S中的状态s，执行DP[4][s] += DP[3][(101000)2 ]（两个状态可达，所以方案数是可传递的，又因为多个不同的状态可能到达同一个状态，所以采用累加的方式）。

根据给定的骨牌，我们可以枚举它的摆放方式，图二-4-5展示了三种骨牌的摆放方式以及能够转移到的状态，但是这里的状态转移还没结束，因为第3行尚未放满，问题求的是将整个棋盘铺满的方案数，所以只有当第i行全部放满后，才能将状态转移给i+1行。