动态规划题目

[转]整理自http://www.cppblog.com/menjitianya/archive/2015/10/23/212084.html

递推

  • [例题1]在一个3 X N的长方形方格中,铺满1X2的骨牌(骨牌个数不限制),给定N,求方案数(图一 -1-1为N=2的所有方案),所以N=2时方案数为3。

  • 二维状态

  • 状态转移方程

    • 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

donggui_5.png

  • [例题2]对一个“01”串进行一次μ变换被定义为:将其中的”0”变成”10”,”1”变成”01”,初始串为”1”,求经过N(N <= 1000)次μ变换后的串中有多少对”00”

  • 要出现”00”,一定是”10”和”01”相邻产生的

  • 设A = “10”, B = “01”,构造出的树形递推图如图所示,如果要出现”00”,一定是AB(”1001”)

donggui_7.png

  • 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],递推求解

记忆化搜索

  • [例题3]这个问题直接给出了一段求函数w(a, b, c)的伪代码:
    1
    2
    3
    4
    5
    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)的值

  • 这个函数的时间复杂度是指数级的(尽管这个三元组的最大元素只有20,这是个陷阱)。对于任意一个三元组(a, b, c)w(a, b, c)可能被计算多次,而对于固定的(a, b, c)w(a, b, c)其实是个固定的值,没必要多次计算,所以只要将计算过的值保存在f[a][b][c]中,整个计算就只有一次了,总的时间复杂度就是O(n^3),这个问题的n只有20

状态和状态转移

最优化原理和最优子结构

  • 【例题4】给定一个长度为n(1 <= n <= 1000)的整数序列a[i],求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列),满足如下条件:
      1. 该序列单调递增;
      1. 在所有满足条件1的序列中长度是最长的;
  • 最长单调子序列

  • 枚举(DFS),即枚举a[i]这个元素取或不取,所有取的元素组成一个合法的子序列,枚举的时候需要满足单调递增这个限制,那么对于一个n个元素的序列,最坏时间复杂度自然就是O(2^n)

  • 假设第i个数取的情况下已经搜索出的最大长度记录在数组d中,即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的长度,那么如果下次搜索得到的序列长度小于等于d[i],就不必往下搜索了(因为即便继续往后枚举,能够得到的解必定不会比之前更长);反之,则需要更新d[i]的值

  • 对于任意的i,d[i]一定等于d[j] + 1 ( j < i ),而且还得满足a[j] < a[i]

  • 状态转移方程:

    • d[i] = max{ d[j] | j < i && a[j] < a[i] } + 1
  • 时间复杂度是O(n^2)

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

  • [例题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

  • 漏算了第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]就是需要求的最小费用

经典模型

线性模型

线性模型的是动态规划中最常用的模型,上文讲到的最长单调子序列就是经典的线性模型,这里的线性指的是状态的排布是呈线性的

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

  • 先将所有人按花费时间递增进行排序,假设前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] }

区间模型

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

  • 典型的区间模型,回文串拥有很明显的子结构特征,即当字符串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)

背包模型

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),下文会介绍滚动数组优化)

完全背包

  • 有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)

多重背包

  • 有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的最大资金。

状态压缩模型

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

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

  • 2、对于路径上相邻的任意两个顶点C_iC_{i+1},累加权值乘积V_i*V_{i+1}
  • 3、对于相邻的三个顶点CiC_{i+1}C_{i+2},如果Ci和C{i+2}之间有边,那么累加权值三乘积``Vi*V{i+1}*V_{i+2}``

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

  • 枚举所有路径,判断找出值最大的,复杂度为O(n!),不可行

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

  • 状态转移方程: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]利用以下两种积木(任意数量,可进行旋转和翻转),拼出一个m*n( 1<= m <= 9, 1 <= n <= 9 )的矩形,问这样的方式有多少种。

donggui_11.png
donggui_12.png

  • m = 2, n = 3的情况有以下5种拼接方式:

donggui_14.png

  • 经典问题,2进制状态压缩

  • 因为第M行的情况总共有2^n,按照这个思路下去,我们发现第i (1 <= i <= m)行的状态顶多也就2^n种,这里的状态可以用一个二进制整数来表示,对于第i行,如果这一行的第j个格子被骨牌填充则这个二进制整数的第j位为1,否则为0

  • 如果我们已知第i行的状态k对应的方案数,并且状态k放置几个骨牌后能够将i+1行的状态变成k’,那么第i+1行的k’这个状态的方案数必然包含了第i行的状态k的方案数,这个放置骨牌的过程就是状态转移

  • 用一个二维数组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,如图所示:

donggui_16.png

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

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

donggui_17.png

  • 枚举摆放的这一步可以采用dfs递归枚举列,递归出口为列数col == N时。dfs函数的原型可以写成如下的形式:
1
2
3
4
5
6
void dfs( int col, int nextrow, int nowstate, int nextstate, LL cnt);
// col 表示当前枚举到的列编号
// nextrow 表示下一行的行编号
// nowstate 表示当前枚举骨牌摆放时第i 行的状态(随着放置骨后会更新)
// nextstate 表示当前枚举骨牌摆放时第i+1行的状态(随着放置骨后会更新)
// cnt 状态转移前的方案数,即第i行在放置骨牌前的方案数
  • 对骨牌进行归类,旋转之后得到如下六种情况:

donggui_18.png

  • 都被圈定在一个2X2的格子里,所以每个骨牌都可以用2个2位的2进制整数来表示,编码方式类似上面的状态表示法
1
2
3
4
5
6
7
8
int blockMask[6][2] = {
{1, 1}, // 竖向2X1
{3, 0}, // 横向1X2
{3, 1}, // 枪
{3, 2}, // 7
{1, 3}, // L
{2, 3}, // J
};
  • blockMask[k][0]表示骨牌第一行的状态,blockMask[k][1]表示骨牌第二行的状态。这样一来就可以通过简单的位运算来判断第k块骨牌是否可以放在(i, col)这个格子上,这里的i表示行编号,col则表示列编号

  • 几种常用的位运算:

    • a. x & (1<<i)值如果非0,表示x这个数字的二进制表示的第i(i >= 0)位为1,否则为0;
    • b. x & (y<<i)值如果非0,表示存在一个p(i <= p < i+k),使得x这个数字的二进制表示的第p位和y的p-i位均为1(k为y的二进制表示的位数);
    • c. x | (1<<i)将x的第i位变成1(当然,有可能原本就为1,这个不影响);
    • d. x | (y<<i)将x的第i~i+k-1位和y进行位或运算(k为y的二进制表示的位数),这一步就是模拟了骨牌摆放;
  • 这个格子可以放置第k个骨牌的条件有如下几个:

    • 1、当前骨牌横向长度记为w,那么w必须满足 col + w <= N,否则就超出右边界了。
    • 2、 nowstate & (blockMask[k][0]<<col) == 0,即第i行,骨牌放入前对应的格子为空(对应的格子表示骨牌占据的格子,下同)
    • 3、nextstate & (blockMask[k][1]<<col) == 0,即第i+1行,骨牌放入前对应的格子为空
    • 4、最容易忽略的一点是,“J”骨牌放置时,它的缺口部分之前必须要被骨牌铺满,否则就无法满足第i行全铺满这个条件了
  • 当四个条件都满足就可以递归进入下一层了,递归的时候也是采用位运算,实现如下:

1
dfs( col+1, nextrow, nowstate|(blockMask[k][0]<<col), nextstate|(blockMask[k][1]<<col), cnt );
  • 这里的位或运算(|)就是模拟将一个骨牌摆放到指定位置的操作(参见位运算d)

  • 在枚举到第col列的时候,有可能(i, col)这个格子已经被上一行的骨牌给“占据”了(是否被占据可以通过 (1<<col) & nowstate 得到),这时候我们只需要继续递归下一层,只递增col,其它量都不变即可,这表示了这个格子什么都不放的情况

树状模型

树形动态规划(树形DP),是指状态图是一棵树,状态转移也发生在树上,父结点的值通过所有子结点计算完毕后得出。

  • [例题11]给定一颗树,和树上每个结点的权值,求一颗非空子树,使得权和最大。

  • d[1][i]表示i这个结点选中的情况下,以i为根的子树的权和最大值;

  • d[0][i]表示i这个结点不选中的情况下,以i为根的子树的权和最大值;

  • 状态转移方程:

    • d[1][i] = v[i] + sum{ d[1][v] | v是i的直接子结点 && d[1][v] > 0 }
    • d[0][i] = max( 0, max{ max( d[0][v], d[1][v] ) | v是i的直接子结点 } )
  • 构造一个以1为根结点的树,然后就可以通过dfs求解

  • 题目要求求出的树为非空树,所以当所有权值都为负数的情况下需要特殊处理,选择所有权值中最大的那个作为答案

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

如果子问题的数目为O(n^t),每个子问题需要用到O(n^e)个子问题的结果,那么我们称它为tD/eD的问题,于是可以总结出四类常用的动态规划方程:(下面会把opt作为取最优值的函数(一般取min或max), w(j, i)为一个实函数,其它变量都可以在常数时间计算出来)。)

    1. 1D/1D : d[i] = opt{ d[j] + w(j, i) | 0 <= i < j } (1 <= i <= n)
    • [例题4]和[例题5]都是这类方程。
    1. 2D/0D : d[i][j] = opt{ d[i-1][j] + xi, d[i][j-1] + yj, d[i-1][j-1] + zij } (1<= i, j <= n)
    • [例题7]是这类方程的变形,最典型的见最长公共子序列问题
    1. 2D/1D : d[i][j] = w(i, j) + opt{ d[i][k-1] + d[k][j] }, (1 <= i < j <= n)
    • 区间模型常用方程。
    • 另外一种常用的2D/1D的方程为: d[i][j] = opt{ d[i-1][k] + w(i, j, k) | k < j } (1<= i <= n, 1 <= j <= m)
    1. 2D/2D : d[i][j] = opt{ d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j}
    • 常见于二维的迷宫问题,由于复杂度比较大,所以一般配合数据结构优化,如线段树、树状数组等

对于一个tD/eD 的动态规划问题,在不经过任何优化的情况下,可以粗略得到一个时间复杂度是O(nt+e),空间复杂度是O(nt)的算法,大多数情况下空间复杂度是很容易优化的,难点在于时间复杂度

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

滚动数组(空间优化)

……