我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划法 >

夜深人静写算法(2):动态规划(上)

归档日期:04-23       文本归类:动态规划法      文章编辑:爱尚语录

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

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

  这是一个经典的递推问题,如果觉得无从下手,我们可以来看一个更加简单的问题,把问题中的“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。

  再回头来看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]呢?

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

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

  从图中观察得出,以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],递推求解。

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

  乍看下只要将伪代码翻译成实际代码,然后直接对于给定的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。

  在介绍递推和记忆化搜索的时候,都会涉及到一个词—状态,它表示了解决某一问题的中间结果,这是一个比较抽象的概念,例如【例题1】中的f[i][j],

  中的FA[i]、FB[i],【例题3】中的f[a][b][c],无论是递推还是记忆化搜索,首先要设计出合适的状态,然后通过状态的特征建立状态转移方程(f[i] = f[i-1] + f[i-2] 就是一个简单的状态转移方程)。

  4、最优化原理和最优子结构在介如果问题的最优解包含的子问题的解也是最优的,就称该问题具有最有子结构,即满足最优化原理。这里我尽力减少理论化的概念,而改用一个简单的例题来加深对这句线】给定一个长度为n(1 = n = 1000)的整数序列a[i],求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列),满足如下条件:

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

  我想到的是万金油算法—枚举(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),所以放弃往下枚举,大大减少了搜索的状态空间。

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

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

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

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

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

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

  我们先将所有人按花费时间递增进行排序,假设前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个人和另外一个人一起过河,由于花费时间最少的人在这边,所以下一次送手电筒过来的一定是花费次少的,送过来后花费最少的和花费次少的一起过河,解决问题)

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

  给定一个长度为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]时,我们将它变成更小的子问题求解,我们有两种决策:

  2、在A[i]前面添加一个字符A[j];根据两种决策列出状态转移方程为:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  枚举所有路径,判断找出值最大的,复杂度为O(n!),取缔!由于点数较少,采用二进制表示状态,用d[i][j][k]表示某条哈密尔顿路径的最大权值,其中i是一个二进制整数,它的第t位为1表示t这个顶点在这条哈密尔顿路径上,为0表示不在路径上。j和k分别为路径的最后两个顶点。那么图二-4-1表示的状态就是:

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

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

  经典问题,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的方案数,这个放置骨牌的过程就是状态转移。

  用一个二维数组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。

  然后再来看如何将骨牌摆上去,这里对骨牌进行归类,旋转之后得到如下六种情况:

  为了方便叙述,分别给每个类型的骨牌强加了一个奇怪的名字,都是按照它自身的形状来命名的,o(╯□╰)o。然后我们发现它们都被圈定在一个2X2的格子里,所以每个骨牌都可以用2个2位的2进制整数来表示,编码方式类似上面的状态表示法(参照图6,如果骨牌对应格子为蓝色则累加格子上的权值),定义如下:

  blockMask[k][0]表示骨牌第一行的状态,blockMask[k][1]表示骨牌第二行的状态。这样一来就可以通过简单的位运算来判断第k块骨牌是否可以放在(i, col)这个格子上,这里的i表示行编号,col则表示列编号。接下来需要用到位运算进行状态转移,所以先介绍几种常用的位运算:

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

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

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

  常见于二维的迷宫问题,由于复杂度比较大,所以一般配合数据结构优化,如线段树、树状数组等。

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

本文链接:http://quangdungfc.net/dongtaiguihuafa/54.html