动态规划

2020年06月05日 阅读数:194
这篇文章主要向大家介绍动态规划,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
目录  

1、动态规划初探
      一、递推
      二、记忆化搜索
      三、状态和状态转移
      四、最优化原理和最优子结构
      五、决策和无后效性

2、动态规划的经典模型
       一、线性模型
       二、区间模型
       三、背包模型
       四、状态压缩模型
       五、树状模型

3、动态规划的经常使用状态转移方程
      一、1D/1D
       二、2D/0D
       三、2D/1D
       四、2D/2D

4、动态规划和数据结构结合的经常使用优化
       一、滚动数组
       二、最长单调子序列的二分优化
       三、矩阵优化
       四、斜率优化
       五、树状数组优化
       六、线段树优化
       七、其余优化

5、动态规划题集整理


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
     二、记忆化搜索
      递推说白了就是在知道前i-1项的值的前提下,计算第i项的值,而记忆化搜索则是另一种思路。它是直接计算第i项,须要用到第 j 项的值( j < i)时去查表,若是表里已经有第 j 项的话,则直接取出来用,不然递归计算第 j 项,而且在计算完毕后把值记录在表中。记忆化搜索在求解多维的状况下比递推更加方便,【例题3】是我遇到的第一个记忆化搜索的问题,记忆犹新。
       【例题3】这个问题直接给出了一段求函数w(a, b, c)的伪代码:
      function w(a, b, c):
       if a <=or b <=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。
     三、状态和状态转移           
      在介绍递推和记忆化搜索的时候,都会涉及到一个词---状态,它表示了解决某一问题的中间结果,这是一个比较抽象的概念,例如【例题1】中的f[i][j],【例题2】中的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或多个元素后的序列),知足以下条件:
      一、该序列单调递增;
      二、在全部知足条件1的序列中长度是最长的;
      这个问题是经典的动态规划问题,被称为最长单调子序列。

      咱们假设如今没有任何动态规划的基础,那么看到这个问题首先想到的是什么?
      我想到的是万金油算法---枚举(DFS),即枚举a[i]这个元素取或不取,全部取的元素组成一个合法的子序列,枚举的时候须要知足单调递增这个限制,那么对于一个n个元素的序列,最坏时间复杂度天然就是O(2 n),n等于30就已经很变态了更别说是1000。可是方向是对的,动态规划求解以前先试想一下搜索的正确性,这里搜索的正确性是很显然的,由于已经枚举了全部状况,总有一种状况是咱们要求的解。咱们尝试将搜索的算法进行一些改进,假设第i个数取的状况下已经搜索出的最大长度记录在数组d中,即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的长度,那么若是下次搜索获得的序列长度小于等于d[i],就没必要往下搜索了(由于即使继续日后枚举,可以获得的解一定不会比以前更长);反之,则须要更新d[i]的值。如图一-4-1,红色路径表示第一次搜索获得的一个最长子序列一、二、三、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】老王想在将来的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]就是咱们须要求的最小费用了。

2、动态规划的经典模型
      一、线性模型
       线性模型的是动态规划中最经常使用的模型,上文讲到的最长单调子序列就是经典的线性模型,这里的线性指的是状态的排布是呈线性的。【例题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] }

       二、区间模型
      区间模型的状态表示通常为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]时,咱们将它变成更小的子问题求解,咱们有两种决策:
      一、在A[j]后面添加一个字符A[i];
      二、在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)的优化算法。

      
三、背包模型
      
背包问题是动态规划中一个最典型的问题之一。因为网上有很是详尽的背包讲解
这里只将经常使用部分抽出来,具体推导过程详见

       
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个物品拆分红容量为一、二、四、八、... 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的最大资金。

      
四、状态压缩模型
      
状态压缩的动态规划,通常处理的是数据规模较小的问题,将状态压缩成k进制的整数,k取2时最为常见。
      
【例题9】
对于一条n
(n <= 11)个点的哈密尔顿路径C1C2...CN(通过每一个点一次的路径)的值由三部分组成:
      一、每一个顶点的权值Vi的和
      二、对于路径上相邻的任意两个顶点CiCi+1,累加权值乘积 Vi*Vi+1
      三、对于相邻的三个顶点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 < 2 n),为了将问题简化,咱们虚拟出一个第0行,则有DP[0][j] = (j == 
2 n
-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行。
图二-4-5
       枚举摆放的这一步能够采用dfs递归枚举列,递归出口为列数col == N时。dfs函数的原型能够写成以下的形式:
       void dfs (  int col ,  int nextrow ,  int nowstate ,  int nextstate , LL cnt ) ;
       // col       表示当前枚举到的列编号
        // nextrow   表示下一行的行编号
        // nowstate  表示当前枚举骨牌摆放时第i  行的状态(随着放置骨后会更新)
        // nextstate 表示当前枚举骨牌摆放时第i+1行的状态(随着放置骨后会更新)
        // cnt       状态转移前的方案数,即第i行在放置骨牌前的方案数
       而后再来看如何将骨牌摆上去,这里对骨牌进行归类,旋转以后获得以下六种状况:
图二-4-6
图二-4-7
       为了方便叙述,分别给每一个类型的骨牌强加了一个奇怪的名字,都是按照它自身的形状来命名的,o(╯□╰)o。而后咱们发现它们都被圈定在一个2X2的格子里,因此每一个骨牌均可以用2个2位的2进制整数来表示,编码方式相似上面的状态表示法(参照图6,若是骨牌对应格子为蓝色则累加格子上的权值),定义以下:

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个骨牌的条件有以下几个:
       一、当前骨牌横向长度记为w,那么w必须知足 col + w <= N,不然就超出右边界了。
       二、 nowstate  (blockMask [k ] [ 0 ]<<col)  == 0,即第i行,骨牌放入前 对应的格子为空( 对应的格子表示骨牌占据的格子,下同)
       三、nextstate  (blockMask [k ] [ 1 ]<<col)  == 0,即第i+1行,骨牌放入前对应的格子为空
       四、最容易忽略的一点是,“J”骨牌放置时,它的缺口部分以前必需要被骨牌铺满,不然就没法知足第i行全铺满这个条件了,如图二-4-8所示的状况。
图二-4-8
       当四个条件都知足就能够递归进入下一层了,递归的时候也是采用位运算,实现以下:
       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】给定一颗树,和树上每一个结点的权值,求一颗非空子树,使得权和最大。php

   

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

      用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求解了。数据结构

      这题题目要求求出的树为非空树,因此当全部权值都为负数的状况下须要特殊处理,选择全部权值中最大的那个做为答案。

app

3、动态规划的经常使用状态转移方程
      
动态规划算法三要素(摘自黑书,总结的很好,颇有归纳性):
              ①全部不一样的子问题组成的表
              ②解决问题的依赖关系能够当作是一个图
              ③填充子问题的顺序(即对
②的图进行
拓扑排序,填充的过程称为状态转移);
      则若是子问题的数目为O(n t
),每一个子问题须要用到
O(n e
)个子问题的结果,那么咱们称它为
tD/eD的问题,因而能够总结出四类经常使用的动态规划方程:
      (下面会把opt做为取最优值的函数(通常取min或max), w(j, i)为一个实函数,其它变量均可以在常数时间计算出来)。)
       一、1D/1D
             d[i] = opt{ d[j] + w(j, i) | 0 <= i < j } (1 <= i <= n)
             【例题4】和【例题5】都是这类方程。
       2
、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】是这类方程的变形,最典型的见最长公共子序列问题。
       3
、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)
       4
、2D/2D
              
d[i][j] = opt{ d[i'][j'] + w(i', j', i, j) |  0 <= i' < i, 0 <= j' < j}
             常见于二维的迷宫问题,因为复杂度比较大,因此通常配合数据结构优化,如线段树、树状数组等。
       对于一个
tD/eD 的动态规划问题,在不通过任何优化的状况下,能够粗略获得一个时间复杂度是
O(n t+e
)
,空间复杂度是O(n t
)
的算法,大多数状况下空间复杂度是很容易优化的,难点在于时间复杂度,下一章咱们将详细讲解各类状况下的动态规划优化算法。

4、动态规划和数据结构结合的经常使用优化
       一、滚动数组
      【例题12】例题7(回文串那题)的N变成5000,其他不变。

       回忆一下那个问题的状态转移方程以下: 
       d[i][j] =   {
                                 d[i+1][j-1]                           | A[i] == A[j] 
                                 
min{ d[i+1][j], d[i][j-1] } + 1  
|  
A[i] 
!= A[j]
                      }
       咱们发现将d[i][j]理解成一个二维的矩阵,i表示行,j表示列,那么第i行的结果只取决于第i+1和第i行的状况,对于第i+2行它表示并不关心,那么咱们只要用一个d[2][N]的数组就能保存状态了,其中d[0][N]为奇数行的状态值,d[1][N]为偶数行的状态值,当前须要计算的状态行数为奇数时,会利用到
d[1][N]的部分状态,奇数行计算完毕,
d[1][N]整行状态都没用了,能够用于下一行状态的保存,相似“传送带”的滚动来循环利用空间资源,美其名曰 - 滚动数组。
       这是个2D/0D问题,理论的空间复杂度是O(n 2),利用滚动数组能够将空间降掉一维,变成O(n)。
       背包问题的几个状态转移方程一样能够用滚动数组进行空间优化。

        
二、最长单调子序列
       
d[i] = max{ d[j] | j < i && a[j] < a[i] } + 1;
       
那个问题的状态转移方程以下:
      
【例题13】例题4(最长递增子序列那题)的N变成100000,其他不变。

       首先明确决策的概念,咱们认为 j 和 k (j < i, k < i)都是在计算d[i]时的两个决策。那么假设他们知足a[j] < a[k
](它们的状态对应就是d[j] 和 d[k]),若是a[i] > a[k],则必然有a[i] > a[j],可以选k作决策的也必然可以选 j 作决策,那么如若此时d[j] >= d[k],显然k不多是最优决策(j的决策始终比它优,以j作决策,a[ j ]的值小但状态值却更大),因此d[k]是不须要保存的。
       
基于以上理论,咱们能够采用二分枚举,维护一个值 (这里的值指的是a[i]) 递增的决策序列,不断扩大决策序列,最后决策的数目就是最长递增子序列的长度。具体作法是:
       
枚举i,若是a[i]比决策序列中最大的元素的值还大,则将i插入到决策序列的尾部;不然二分枚举决策序列,找出其中值最小的一个决策k,而且知足a[k] > a[i],而后用决策i替换决策k。
       
这是个1
D/1D问题,理论的时间复杂度是O(n 2),利用单调性优化后能够将复杂度将至O(nlogn)。

      【例题14】
给定n个元素(n <= 100000)的序列,将序列的全部数分红x堆,每堆都是单调不增的,求x的最小值。
       结论:能够转化成求原序列的最长递增子序列。
       证实:由于这x堆中每堆元素都是单调不增的,因此原序列的最长递增子序列的每一个元素在分出来的每堆元素中必定只出现最多一个,那么最长递增子序列的长度L的最大值为x,因此x >= L。
而咱们要求的是x的最小值,因而这个最小值就是 L 了。

       
三、矩阵优化
      
【例题15】三个小岛,编号一、二、3,老王第0天在1号岛上。这些岛有一些奇怪的规则,每过1天,1号岛上的人必须进入二、3号岛;2号岛上的人必须进入1号岛;3号岛上的人能够前往一、2或留在3号岛
。问第n(n <=
10 9
)天老王在到达1号岛的行走方案,因为数据比较大,只须要输出 ans MOD 100000007的值便可。
图四-3-1
       
临时想的一个问题,首先看问题有几个维度,岛和天数,并且状态转移是常数级的,因此这是个2D/0D问题,咱们用f[i][j]表示第i天在j号岛上的方案数,那么初始状态f[0][1] = 1, f[0][2] = f[0][3] = 0。
       
状态转移能够参考图四-3-1,有:
       
f[i][1] = f[i-1][2] + f[i-1][3]
       
f[i][2] = f[i-1][1] + f[i-1][3]
       
f[i][3] = f[i-1][1] + f[i-1][3] 
       
图四-3-2
       
令这个矩阵为A,Aij表示从i号岛到j号岛是否连通,连通标1,不连通标0,它还有另一个含义,就是通过1天,从i岛到j岛的方案数,利用矩阵的传递性,
A 2的第i行的第j列则表示通过2天,从i岛到j岛的方案数,一样的,
A n 
则表示了通过n天,从i岛到j岛的方案数,那么问题就转化成了求A n 
MOD 100000007的值了。
       
An
当n为偶数的时候等于(
An/2
)*(A
n/2
);当n为奇数的时候,等于(
An/2
)*