动态规划 订阅
动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 [1]  。 展开全文
动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 [1]  。
信息
运    用
求解决策过程(decision process)最优化的数学方法
外文名
dynamic programming
简    称
DP
中文名
动态规划
学    科
运筹学
第一本著作
《Dynamic Programming》
动态规划简介
动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便 [2]  。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解 [2]  。在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策问题。在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化的过程为动态规划方法 [3]  。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式 [4]  。1. 多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题 [5]  。各个阶段的决策构成一个决策序列,称为一个策略。每一个阶段都有若干个决策可供选择,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定。策略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,使在预定的标准下达到最好的效果 [5]  。2.动态规划问题中的术语阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的 [5]  。状态:状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点 [5]  。无后效性:我们要求状态具有下面的性质:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性 [5]  。决策:一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多问题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史 [5]  。决策变量的范围称为允许决策集合 [5]  。策略:由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合 [5]  。允许策略集合中达到最优效果的策略称为最优策略 [5]  。给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与x(k+1)确定的对应关系,用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律,称为状态转移方程 [5]  。最优化原理:作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略” [5]  。最优性原理实际上是要求问题的最优策略的子策略也是最优 [5]  。多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法 [6]  。任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性 [7]  。1、最优化原理(最优子结构性质)最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 [7]  。2、无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性 [7]  。3、子问题的重叠性动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间 [7]  。
收起全文
精华内容
参与话题
问答
  • 系列课程基于主讲者多年来教授计算机专业大一学生程序设计课的教学经验,准确把握知识点,注重教学视频与实践体系的结合,帮助初学者顺利掌握知识,获得学习中的自信。本部分“进阶篇”的目标,是使学习者学会运用多...
  • 教你彻底学会动态规划——入门篇

    万次阅读 多人点赞 2015-08-11 13:26:41
    动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是...

        动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章,大多都是叙述概念,讲解原理,让人觉得晦涩难懂,即使一时间看懂了,发现当自己做题的时候又会觉得无所适从。我觉得,理解算法最重要的还是在于练习,只有通过自己练习,才可以更快地提升。话不多说,接下来,下面我就通过一个例子来一步一步讲解动态规划是怎样使用的,只有知道怎样使用,才能更好地理解,而不是一味地对概念和原理进行反复琢磨。

        首先,我们看一下这道题(此题目来源于北大POJ):

        数字三角形(POJ1163)

       

        在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径。 三角形的行数大于1小于等于100,数字为 0 - 99

        输入格式:

        5      //表示三角形的行数    接下来输入三角形

        7

        3   8

        8   1   0

        2   7   4   4

        4   5   2   6   5

        要求输出最大和

        接下来,我们来分析一下解题思路:

        首先,肯定得用二维数组来存放数字三角形

        然后我们用D( r, j) 来表示第r行第 j 个数字(r,j从1开始算)

        我们用MaxSum(r, j)表示从D(r,j)到底边的各条路径中,最佳路径的数字之和。

        因此,此题的最终问题就变成了求 MaxSum(1,1)

        当我们看到这个题目的时候,首先想到的就是可以用简单的递归来解题:

        D(r, j)出发,下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形,我们可以写出如下的递归式:   

    if ( r == N)                
    	MaxSum(r,j) = D(r,j)  
    else      
    	MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j) 

        根据上面这个简单的递归式,我们就可以很轻松地写出完整的递归代码: 

    #include <iostream>  
    #include <algorithm> 
    #define MAX 101  
    using namespace std; 
    int D[MAX][MAX];  
    int n;  
    int MaxSum(int i, int j){    
    	if(i==n)  
    		return D[i][j];    
    	int x = MaxSum(i+1,j);    
    	int y = MaxSum(i+1,j+1);    
    	return max(x,y)+D[i][j];  
    }
    int main(){    
    	int i,j;    
    	cin >> n;    
    	for(i=1;i<=n;i++)   
    		for(j=1;j<=i;j++)        
    			cin >> D[i][j];    
    	cout << MaxSum(1,1) << endl;  
    }      

        对于如上这段递归的代码,当我提交到POJ时,会显示如下结果:

       

        对的,代码运行超时了,为什么会超时呢?

        答案很简单,因为我们重复计算了,当我们在进行递归时,计算机帮我们计算的过程如下图:

        

        就拿第三行数字1来说,当我们计算从第2行的数字3开始的MaxSum时会计算出从1开始的MaxSum,当我们计算从第二行的数字8开始的MaxSum的时候又会计算一次从1开始的MaxSum,也就是说有重复计算。这样就浪费了大量的时间。也就是说如果采用递规的方法,深度遍历每条路径,存在大量重复计算。则时间复杂度为 2的n次方,对于 n = 100 行,肯定超时。 

        接下来,我们就要考虑如何进行改进,我们自然而然就可以想到如果每算出一个MaxSum(r,j)就保存起来,下次用到其值的时候直接取用,则可免去重复计算。那么可以用n方的时间复杂度完成计算。因为三角形的数字总数是 n(n+1)/2

        根据这个思路,我们就可以将上面的代码进行改进,使之成为记忆递归型的动态规划程序: 

    #include <iostream>  
    #include <algorithm> 
    using namespace std;
     
    #define MAX 101
      
    int D[MAX][MAX];    
    int n;  
    int maxSum[MAX][MAX];
     
    int MaxSum(int i, int j){      
    	if( maxSum[i][j] != -1 )         
    		return maxSum[i][j];      
    	if(i==n)   
    		maxSum[i][j] = D[i][j];     
    	else{    
    		int x = MaxSum(i+1,j);       
    		int y = MaxSum(i+1,j+1);       
    		maxSum[i][j] = max(x,y)+ D[i][j];     
    	}     
    	return maxSum[i][j]; 
    } 
    int main(){    
    	int i,j;    
    	cin >> n;    
    	for(i=1;i<=n;i++)   
    		for(j=1;j<=i;j++) {       
    			cin >> D[i][j];       
    			maxSum[i][j] = -1;   
    		}    
    	cout << MaxSum(1,1) << endl; 
    } 

        当我们提交如上代码时,结果就是一次AC

       

        虽然在短时间内就AC了。但是,我们并不能满足于这样的代码,因为递归总是需要使用大量堆栈上的空间,很容易造成栈溢出,我们现在就要考虑如何把递归转换为递推,让我们一步一步来完成这个过程。

        我们首先需要计算的是最后一行,因此可以把最后一行直接写出,如下图:

       

        现在开始分析倒数第二行的每一个数,现分析数字2,2可以和最后一行4相加,也可以和最后一行的5相加,但是很显然和5相加要更大一点,结果为7,我们此时就可以将7保存起来,然后分析数字7,7可以和最后一行的5相加,也可以和最后一行的2相加,很显然和5相加更大,结果为12,因此我们将12保存起来。以此类推。。我们可以得到下面这张图:

       

        然后按同样的道理分析倒数第三行和倒数第四行,最后分析第一行,我们可以依次得到如下结果:

       

       

        上面的推导过程相信大家不难理解,理解之后我们就可以写出如下的递推型动态规划程序: 

    #include <iostream>  
    #include <algorithm> 
    using namespace std; 
    
    #define MAX 101  
    
    int D[MAX][MAX];   
    int n;  
    int maxSum[MAX][MAX]; 
    int main(){    
    	int i,j;    
    	cin >> n;    
    	for(i=1;i<=n;i++)   
    		for(j=1;j<=i;j++)        
    			cin >> D[i][j];   
    	for( int i = 1;i <= n; ++ i )     
    		maxSum[n][i] = D[n][i];   
    	for( int i = n-1; i>= 1;  --i )     
    		for( int j = 1; j <= i; ++j )         
    			maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];    
    	cout << maxSum[1][1] << endl;  
    } 

         我们的代码仅仅是这样就够了吗?当然不是,我们仍然可以继续优化,而这个优化当然是对于空间进行优化,其实完全没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推,那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。

         对于空间优化后的具体递推过程如下:

       

       

       

       

       

       

        接下里的步骤就按上图的过程一步一步推导就可以了。进一步考虑,我们甚至可以连maxSum数组都可以不要,直接用D的第n行直接替代maxSum即可。但是这里需要强调的是:虽然节省空间,但是时间复杂度还是不变的。

        依照上面的方式,我们可以写出如下代码:    

     

    #include <iostream>  
    #include <algorithm> 
    using namespace std; 
    
    #define MAX 101  
    
    int D[MAX][MAX];  
    int n; 
    int * maxSum; 
    
    int main(){    
    	int i,j;    
    	cin >> n;    
    	for(i=1;i<=n;i++)   
    		for(j=1;j<=i;j++)        
    			cin >> D[i][j];   
    	maxSum = D[n]; //maxSum指向第n行    
    	for( int i = n-1; i>= 1;  --i )     
    		for( int j = 1; j <= i; ++j )       
    			maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j];    
    	cout << maxSum[1] << endl;  
    }

     

     

     

     

     

        接下来,我们就进行一下总结:

        递归到动规的一般转化方法

        递归函数有n个参数,就定义一个n维的数组,数组的下标是递归函数参数的取值范围,数组元素的值是递归函数的返回值,这样就可以从边界值开始, 逐步填充数组,相当于计算递归函数值的逆过程。

        动规解题的一般思路

        1. 将原问题分解为子问题

    •     把原问题分解为若干个子问题,子问题和原问题形式相同或类似,只不过规模变小了。子问题都解决,原问题即解决(数字三角形例)。
    •     子问题的解一旦求出就会被保存,所以每个子问题只需求 解一次。

        2.确定状态

    •     在用动态规划解题时,我们往往将和子问题相关的各个变量的一组取值,称之为一个“状 态”。一个“状态”对应于一个或多个子问题, 所谓某个“状态”下的“值”,就是这个“状 态”所对应的子问题的解。
    •     所有“状态”的集合,构成问题的“状态空间”。“状态空间”的大小,与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里,一共有N×(N+1)/2个数字,所以这个问题的状态空间里一共就有N×(N+1)/2个状态。

        整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个“状态”只需要经过一次,且在每个状态上作计算所花的时间都是和N无关的常数。

        3.确定一些初始状态(边界状态)的值

        以“数字三角形”为例,初始状态就是底边数字,值就是底边数字值。

        4. 确定状态转移方程

         定义出什么是“状态”,以及在该“状态”下的“值”后,就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”,求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示,此递推公式也可被称作“状态转移方程”。

        数字三角形的状态转移方程:

       
     

        能用动规解决的问题的特点

        1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的,我们就称该问题具有最优子结 构性质。

        2) 无后效性。当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。

     

    好久没看博客发现这篇文章现在已经这么火热了,看了一下评论发现不少人对这篇文章都比较有兴趣,我当初写这篇文章是受到了Coursera上面一门算法课程的启发,大家有兴趣可以去听听这门课程数据结构与算法

     

    展开全文
  • 动态规划的重要性就不多说,直接进入正题 首先,我们看一下官方定义: 定义: 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 动态规划算法的基本思想与...

    首先,本博客为原创作品,欢迎指导,随意转载,如果可以请转载时说明出处,附上本文链接(https://blog.csdn.net/ailaojie/article/details/83014821),谢谢
    原文链接
    动态规划的重要性就不多说,直接进入正题

    首先,我们看一下官方定义:
    定义:
    动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
    动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
    基本思想与策略编辑:
    由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
    (来自百度百科)
    说实话,没有动态规划的基础很难看懂,但是也能从中看出一些信息,下面我翻译成人话:
    首先是拆分问题,我的理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现.
    关键就是这个步骤,动态规划有一类问题就是从后往前推到,有时候我们很容易知道:如果只有一种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前一步推导,得到前一步的最佳选择
    然后就是定义问题状态和状态之间的关系,我的理解是前面拆分的步骤之间的关系,用一种量化的形式表现出来,类似于高中学的推导公式,因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态转移方程式)
    我们再来看定义的下面的两段,我的理解是比如我们找到最优解,我们应该讲最优解保存下来,为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每一次都把最优解保存了下来,大大降低了时间复杂度

    说很难理解清楚,容易懵懵懂懂的,所以下面结合实例看一下(建议结合实例,纸上谈兵不太好):

    经典的数字三角形问题(简单易懂,经典动态规划);

    题目:题目描述
    输入格式
    可以看出每走第n行第m列时有两种后续:向下或者向右下
    由于最后一行可以确定,当做边界条件,所以我们自然而然想到递归求解
    解题思路:解题思路
    c语言答案
    下面简单写一下java代码:

    //java代码纯属自己练习,标准答案参考上面的c语言答案
    class solution{
    	public int getMax(){
    		int MAX = 101;
    		int[][] D = new int[MAX][MAX];   //存储数字三角形
    		int n;              //n表示层数
    		int i = 0; int j = 0;
    		int maxSum = getMaxSum(D,n,i,j);
    		return maxSum;
    	}
    	public int getMaxSum(int[][] D,int n,int i,int j){
    		if(i == n){
    			return D[i][j];
    		}
    		int x = getMaxSum(D,n,i+1,j);
    		int y = getMaxSum(D,n,i+1,j+1);
    		return Math.max(x,y)+D[i][j];
    	}
    }
    

    其实仔细观察,上面的解答过程时间复杂度难以想象的大,那是因为他对有的数字的解进行了多次的重复计算,具体如下图:
    超时原因
    如果不明白上图,可以把每条路径都画出来,观察每个数字有多少条路径经过了他,就会一目了然
    然后我们就可以自然而然的想到,如果我们每次都把结果保存下来,复杂度就会大大降低
    改进方法
    其实答案很简单:改进解法
    其实这是动态规划很精髓的一部分,是减少复杂度的主要原因
    我们都知道,递归一般情况下是可以转化为递推的,不详细解释了,贴上答案:
    递推解法
    其实,仔细观察该解题过程,该过程就是标准的动态规划解题过程,如果把该过程画出来(找到每一步的最优解,其他的舍弃)对动态规划会有更深刻的解法
    还有就是,递推的另一个好处是可以进行空间优化,如图:
    空间优化
    下面总结一下动态规划的解题一般思路:
    首先递归应该是我们解决动态规划问题最常用的方法,帅,速度不算太慢
    那么递归到动规的一般转化方法为:
    如果该递归函数有n个参数,那么就定义一个n维数组,数组下标是递归函数参数的取值范围(也就是数组每一维的大小).数组元素的值就是递归函数的返回值(初始化为一个标志值,表明还未被填充),这样就可以从边界值开始逐步的填充数组,相当于计算递归函数的逆过程(这和前面所说的推导过程应该是相同的).
    原文链接:https://blog.csdn.net/ailaojie/article/details/83014821

    动规解题的一般思路(标准官方,不过经过前边讲解应该就能理解了):

    1. 将原问题分解为子问题(开头已经介绍了怎么分解) (注意:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了; 2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)
    2. 确定状态(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间".我的理解就是状态就是某个问题某组变量,状态空间就是该问题的所有组变量) 另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间
    3. 确定一些初始状态(边界条件)的值 (这个视情况而定,千万别以为就是最简单的那个子问题解,上面只是例子,真正实践动规千变万化)
    4. 确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推,由已知推未知)

    适合使用动规求解的问题:
    1,问题具有最优子结构
    2,无后效性 说的花里胡哨的,其实一般遇到求最优解问题一般适合使用动态规划

    部分参考资料出自:北大信科郭炜老师

    感觉自己洋洋洒洒写了几个小时,对动态规划有了一定的理解,也希望对你们有所帮助,动态规划千变万化,这仅仅是一个理解过程,我们还是应该多练习,共勉吧.转载的话,如果方便请加上转载地址,谢谢.

    展开全文
  • 六大算法之三:动态规划

    万次阅读 多人点赞 2018-06-16 22:03:33
    已知问题规模为n的前提A,求解一个未知解B。(我们用An表示“问题规模为n的已知条件”)此时,如果把问题规模降到0,即已知A0,可以得到A0-&gt;B.如果从A0添加一个元素,得到A1的变化过程。...

    已知问题规模为n的前提A,求解一个未知解B。(我们用An表示“问题规模为n的已知条件”)

    此时,如果把问题规模降到0,即已知A0,可以得到A0->B.

    • 如果从A0添加一个元素,得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理,也就是我们经常使用的数学归纳法;
    • 对于Ai+1,只需要它的上一个状态Ai即可完成整个推理过程(而不需要更前序的状态)。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。

    然而,Ai与Ai+1往往不是互为充要条件,随着i的增加,有价值的前提信息越来越少,我们无法仅仅通过上一个状态得到下一个状态,因此可以采用如下方案:

    • {A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,...,Ai}->Ai+1. 这种方式就是第二数学归纳法。
    • 对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。

    上述两种状态转移图如下图所示:

                 

    能用动规解决的问题的特点 

    能采用动态规划求解的问题的一般要具有3个性质:

        (1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。

        (2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

       (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势

    动规解题的一般思路   

     动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。

        初始状态→│决策1│→│决策2│→…→│决策n│→结束状态

                          图1 动态规划决策过程示意图

        (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。

        (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

        (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程

        (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

        一般,只要解决问题的阶段状态状态转移决策确定了,就可以写出状态转移方程(包括边界条件)。

    实际应用中可以按以下几个简化的步骤进行设计:

        (1)分析最优解的性质,并刻画其结构特征。

        (2)递归的定义最优解。

        (3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值

        (4)根据计算最优值时得到的信息,构造问题的最优解

    算法实现的说明

        动态规划的主要难点在于理论上的设计,也就是上面4个步骤的确定,一旦设计完成,实现部分就会非常简单。

         使用动态规划求解问题,最重要的就是确定动态规划三要素

        (1)问题的阶段 (2)每个阶段的状态

        (3)从前一个阶段转化到后一个阶段之间的递推关系

         递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处

        确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

              f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

    算法实现的步骤

    1、创建一个一维数组或者二维数组,保存每一个子问题的结果,具体创建一维数组还是二维数组看题目而定,基本上如果题目中给出的是一个一维数组进行操作,就可以只创建一个一维数组,如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值,比如背包问题中的不同物体的体积与总体积,找零钱问题中的不同面值零钱与总钱数,这样就需要创建一个二维数组。

    注:需要创建二维数组的解法,都可以创建一个一维数组运用滚动数组的方式来解决,即一位数组中的值不停的变化,后面会详细徐叙述

    2、设置数组边界值,一维数组就是设置第一个数字,二维数组就是设置第一行跟第一列的值,特别的滚动一维数组是要设置整个数组的值,然后根据后面不同的数据加进来变幻成不同的值。

    3、找出状态转换方程,也就是说找到每个状态跟他上一个状态的关系,根据状态转化方程写出代码。

    4、返回需要的值,一般是数组的最后一个或者二维数组的最右下角。

    代码基本框架:

    for(j=1; j<=m; j=j+1) // 第一个阶段
        xn[j] = 初始值;
     
      for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
        for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
          xi[j]=j=max(或min){g(xi-[j1:j2]), ......, g(xi-1[jk:jk+1])};
     
     t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案
     
     print(x1[j1]);
     
     for(i=2; i<=n-1; i=i+1)
     {  
          t = t-xi-1[ji];
     
          for(j=1; j>=f(i); j=j+1)
             if(t=xi[ji])
                  break;}

    下面通过几个典型例子,从简单到难帮助我们理解动态规划。

    1、斐波那契数列

    斐波那契数列大家都很熟悉,而且知道用递归可以很容易的做出来

        if(n == 0){
    	return 0;
        }else if(n == 1){
    	return 1;
        }else{
    	return solutionFibonacci(n-1)+solutionFibonacci(n-2);
        }

    如果用动态规划,就是把结果存到一个数组中。

    public static int solutionFibonacci(int n){
    		if(n==0){
    			return 0;
    		}else if(n == 1){
    			return 1;
    		}else{
    			int result[] = new int[n+1];
    			result[0] = 0;
    			result[1] = 1;
    			for(int i=2;i<=n;i++){
    				result[i] = result[i-1] + result[i-2];
    			}
    			return result[n];
    		}

    与之类似的还有:跳台阶问题:每次只能跳一个或者两个台阶,跳到n层台阶上有几种方法

    填充长方体问题:将一个2*1的长方体填充到2*n的长方体中,有多少种方法

    2、数组最大不连续递增子序列

    arr[] = {3,1,4,1,5,9,2,6,5}的最长递增子序列长度为4。即为:1,4,5,9

    设置一个数组temp,长度为原数组长度,数组第i个位置上的数字代表0...i上最长递增子序列,当增加一个数字时,最大递增子序列可能变成前面最大的递增子序列+1,也可能就是前面最大递增子序列,这需要让新增加进来的数字arr[i]跟前面所有数字比较大小,即当 arr[i] > arr[j],temp[i] = max{temp[j]}+1,其中,j 的取值范围为:0,1...i-1,当 arr[i] < arr[j],temp[i] = max{temp[j]},j 的取值范围为:0,1...i-1,所以在状态转换方程为temp[i]=max{temp[i-1], temp[i-1]+1}

    public static int MaxChildArrayOrder(int a[]) {
    		int n = a.length;
    		int temp[] = new int[n];//temp[i]代表0...i上最长递增子序列
    		for(int i=0;i<n;i++){
    			temp[i] = 1;//初始值都为1
    		}
    		for(int i=1;i<n;i++){
    			for(int j=0;j<i;j++){
    				if(a[i]>a[j]&&temp[j]+1>temp[i]){
    					//如果有a[i]比它前面所有的数都大,则temp[i]为它前面的比它小的数的那一个temp+1取得的最大值
    					temp[i] = temp[j]+1;
    				}
    			}
    		}
    		int max = temp[0];
    		//从temp数组里取出最大的值
    		for(int i=1;i<n;i++){
    			if(temp[i]>max){
    				max = temp[i];
    			}
    		}
    		return max;
    	}

    3、数组最大连续子序列和

    如arr[] = {6,-1,3,-4,-6,9,2,-2,5}的最大连续子序列和为14。即为:9,2,-2,5

    创建一个数组a,长度为原数组长度,不同位置数字a[i]代表0...i上最大连续子序列和,a[0]=arr[0]设置一个最大值max,初始值为数组中的第一个数字。当进来一个新的数字arr[i+1]时,判断到他前面数字子序列和a[i]+arr[i+1]跟arr[i+1]哪个大,前者大就保留前者,后者大就说明前面连续数字加起来都不如后者一个新进来的数字大,前面数字就可以舍弃,从arr[i+1]开始,每次比较完都跟max比较一下,最后的max就是最大值。

    public static int MaxContinueArraySum(int a[]) {
    		int n = a.length;
    		int max = a[0];
    		int sum = a[0];
    		for(int i=1;i<n;i++){
    			sum = Math.max(sum+a[i], a[i]);
    			if(sum>=max){
    				max = sum;
    			}
    		}
    		return max;
    	}

    4、数字塔从上到下所有路径中和最大的路径

    数字塔是第i行有i个数字组成,从上往下每个数字只能走到他正下方数字或者正右方数字,求数字塔从上到下所有路径中和最大的路径,如有下数字塔

    3

    1    5

    8    4    3

    2    6    7    9

    6    2    3    5    1

    最大路径是3-5-3-9-5,和为25。我们可以分别从从上往下看跟从下往上看两种动态规划的方式去解这个题

    从上往下看:当从上往下看时,每进来新的一行,新的一行每个元素只能选择他正上方或者左左方的元素,也就是说,第一个元素只能连他上方的元素,最后一个元素只能连他左上方的元素,其他元素可以有两种选择,所以需要选择加起来更大的那一个数字,并把这个位置上的数字改成相应的路径值,具体过程如下图所示

    3                            3                            3                            3

    1    5                      4    8                      4    8                      4    8

    8    4    3                8    4    3                12   12  11             12   12   11  

    2    6    7    9          2    6    7    9           2    6    7    9         14   18   19   20

    6    2    3    5    1    6    2    3    5    1     6    2    3    5    1    20   20   22   25   21

    所以最大值就是最底层的最大值也就是25。

    具体运算过程就是,建立一个n*n的二维数组dp[][],n是数字塔最后一行的数字个数,二维数组每一行数字跟数字塔每一行数字个数一样,保存的值是从上方到这一个位置最大路径的值,填入边界值dp[0][0]=3,每一行除了第一个值跟最后一个值,其他的值选择上方或者左上方更大的值与这个位置上的值相加得来的值,即dp[i][j]=Math.max(dp[i-1][j-1], dp[i-1][j]) + n[i][j]

    public static int minNumberInRotateArray(int n[][]) {
    		int max = 0;
    		int dp[][] = new int[n.length][n.length];
    		dp[0][0] = n[0][0];
    		for(int i=1;i<n.length;i++){
    			for(int j=0;j<=i;j++){
    				if(j==0){
    					//如果是第一列,直接跟他上面数字相加
    					dp[i][j] = dp[i-1][j] + n[i][j];
    				}else{
    					//如果不是第一列,比较他上面跟上面左面数字谁大,谁大就跟谁相加,放到这个位置
    					dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + n[i][j];
    				}
    				max = Math.max(dp[i][j], max);
    			}
    		}
    		return max;
    	}

    优化:动态规划中每一个需要创建一个二维数组的解法,都可以换成只创建一个一维数组的滚动数组解法,依据的规则是一般二维数组中存放的是所有的结果,但是一般我们需要的结果实在二维数组的最后一行的某个值,前面几行的值都是为了得到最后一行的值而需要的,所以可以开始就创建跟二维数组最后一行一样大的一维数组,每次存放某一行的值,下一次根据这一行的值算出下一行的值,在存入这个数组,也就是把这个数组滚动了,最后数组存储的结果就是原二维数组中最后一行的值。

    拿到本题来说,开始创建一个一维数组dp[n],初始值只有dp[0]=3,新进来一行时,仍然遵循dp[i][j]=Math.max(dp[i-1][j-1], dp[i-1][j]) + n[i][j],现在为求dp[j],所以现在dp[i-1][j]其实就是数组中这个位置本来的元素即dp[j],而dp[i-1][j-1]其实就是数组中上一个元素dp[j-1],也就是说dp[j]=Math.max(dp[j], dp[j-1])+n[i][j]

    public static int minNumberInRotateArray2(int n[][]) {
    		int[] temp = new int[n.length];
    		temp[0] = n[0][0];
    		for(int i=1;i<n.length;i++){
    			for(int j=i;j>=0;j--){
    				if(j==i){
    					temp[i]=temp[i-1]+n[i][j];
    				}else if(j==0){
    					temp[0]+=n[i][0];
    				}else{
    					temp[j]=Math.max(temp[j], temp[j-1])+n[i][j];
    				}
    			}
    		}
    		int max = temp[0];
    		//从temp数组里取出最大的值
    		for(int i=1;i<temp.length;i++){
    			if(temp[i]>max){
    				max = temp[i];
    			}
    		}
    		return max;
    	}

    这样空间复杂度就大幅度下降了。

    从下往上看时:从下往上看时大体思路跟从上往下看一样,但是要简单一些,因为不用考虑边界数据,从下往上看时,每进来上面一行,上面一行每个数字有两条路径到达下面一行,所以选一条最大的就可以

    3                            3                            3                           25

    1    5                      1    5                      1    5                     18   22

    8    4    3                8    4    3                17  16  17              17  16  17  

    2    6    7    9          8    9    12  14         8    9   12  14         8    9    12  14

    6    2    3    5    1    6    2    3    5    1     6    2    3    5    1    6    2    3    5    1

    所以最大值就是最上面数字就是25.

    具体方法也是建立一个二维数组,最下面一行数据添到二维数组最后一行,从下往上填数字,所以状态转化方程是dp[i][j]=Math.max(dp[i+1][j+1], dp[i+1][j]) + n[i][j],具体解决方法跟从上往下看一样,就不写具体代码了。

    优化:滚动数组,只创建一个一维数组,数组初始值是数字塔最下面一行的值,每次新加一行值,将数组中的值改变,最后数组中第一个数字就是最大路径的值。状态转化方程就是temp[j] = Math.max(temp[j], temp[j+1])+n[i][j]。具体代码如下

    public static int minNumberInRotateArray3(int n[][]) {
    		int[] temp = new int[n.length];
    		for(int i=0;i<n.length;i++){
    			temp[i] = n[n.length-1][i];
    		}
    		for(int i=n.length-2;i>=0;i--){
    			for(int j=0;j<=i;j++){
    				temp[j] = Math.max(temp[j], temp[j+1])+n[i][j];
    			}
    		}
    		return temp[0];
    	}

    从下往上看跟从上往下看相比,虽然逻辑较为简单,但是从下往上看时需要得到完整的数字塔之后才能开始计算,而从上往下看时可以随着数字塔的深入来计算,也可以返回任意一层的结果,是最好的方法。

    5、两个字符串最大公共子序列

    比如字符串1:BDCABA;字符串2:ABCBDAB,则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA

    具体思想:设 X=(x1,x2,.....xn)和 Y={y1,y2,.....ym} 是两个序列,将 X 和 Y 的最长公共子序列记为LCS(X,Y),如果 xn=ym,即X的最后一个元素与Y的最后一个元素相同,这说明该元素一定位于公共子序列中。因此,现在只需要找:LCS(Xn-1,Ym-1)就好,LCS(X,Y)=LCS(Xn-1,Ym-1)+1;如果xn != ym,这下要麻烦一点,因为它产生了两个子问题:LCS(Xn-1,Ym) 和 LCS(Xn,Ym-1)。

    动态规划解法:先创建一个解空间即数组,因为给定的是两个字符串即两个一维数组存储的数据,所以要创建一个二维数组,设字符串X有n个值,字符串Y有m个值,需要创建一个m+1*n+1的二维数组,二维数组每个位置(i,j)代表当长度为i的X子串与长度为j的Y的子串他们的最长公共子串,之所以要多创建一个是为了将边界值填入进去,边界值就是第一行跟第一列,指X长度为0或者Y长度为0时,自然需要填0,其他位置填数字时,当这两个位置数字相同,dp[i][j] = dp[i-1][j-1]+1;当这两个位置数字不相同时,dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])。最后二维数组最右下角的值就是最大子串。

    public class MaxTwoArraySameOrder {
    	public static int MaxTwoArraySameOrderMethod(String str1,String str2) {
    		int m = str1.length();
    		int n = str2.length();
    		/*
    		 * 定义一个二维数组保存公共子序列长度
    		 * dp[i][j]表示字符串1从头开始长度是i,字符串2从头开始长度是j,这两个字符串的最长公共子序列的长度
    		 * 设置数组行列比他们长度大一往二维数组中填写数字时,每个位置的数字跟他上方或者左方或者左上方数字有关系,这样处理边界数字时不用处理这种情况,方便接下来的循环
    		 */
    		int dp[][] = new int[m+1][n+1];
    		/*
    		 * 初始化第一行第一列
    		 * dp[0,j]表示啥?表示字符串1的长度是0,字符串2的长度是j,这两个字符串的最长公共子序列的长度是0,因为,字符串1 根本就没有嘛
    		 */
    		for(int i=0;i<=m;i++){
    			dp[i][0] = 0;
    		}
    		for(int i=0;i<=n;i++){
    			dp[0][i] = 0;
    		}
    		for(int i=1;i<=m;i++){
    			for(int j=1;j<=n;j++){
    				/*
    				 * 如果当c[i][j]时,字符串1从头开始长度是i,字符串2从头开始长度是j时他们最后一个字符相同
    				 * 就同时把他们向前移动一位,找c[i-1][j-1]时长度最大的再加一
    				 * 表现在二维数组中就是c[i][j]左上方的点
    				 */
    				if(str1.charAt(i-1) == str2.charAt(j-1)){
    					dp[i][j] = dp[i-1][j-1]+1;
    					/*
    					 * 如果当c[i][j]时,他们最后一个字符不相同
    					 * 要将str1往前移动一位的c[i-1][j]的lcs长度,或者将str2往前移动一位的c[i][j-1]的lcs长度
    					 * 哪个长,将它赋给c[i][j]
    					 * 表现在二维数组中就是c[i][j]上方的点或者左方的点
    					 */
    				}else{
    					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
    				}
    			}
    		}
    		return dp[m][n];
    	}
    	public static void main(String[] args) {
    		String str1 = "BDCABA";
    		String str2 = "ABCBDAB";
    		int array = MaxTwoArraySameOrderMethod(str1,str2);
    		System.out.println(array);
    	}
    
    }

    6、背包问题

    在N件物品取出若干件放在容量为W的背包里,每件物品的体积为W1,W2……Wn(Wi为整数),与之相对应的价值为P1,P2……Pn(Pi为整数),求背包能够容纳的最大价值。

    像这种固定数值的组合问题,比如这个问题的W总容量,跟下个实例零钱问题的总钱数,都是适合用动态规划来解决的问题,对于这样的问题,动态规划的解法就是:创建一个二维数组,横坐标是从1开始到W,纵坐标是组成W的各种元素,本题中就是指W1,W2……Wn,数组中每个位置(i,j)的数字就是当组成元素只有W1,W2……Wi,背包可放容量为j时的结果,本题中就是容纳的最大价值。所以很容易分析出,当(i,j)时,如果Wi能放的下,空间减小,但是会增加Pi的价值,如果Wi不能放的下,空间不变,是(i-1,j)的价值,取其中最大值就好了,即状态转化方程为能放的下,dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);放不下,dp[i][j] = dp[i-1][j];

    public static int PackageHelper(int n,int w[],int p[],int v) {
    		//设置一个二维数组,横坐标代表从第一个物品开始放到第几个物品,纵坐标代表背包还有多少容量,dp代表最大价值
    		int dp[][] = new int[n+1][v+1];
    		for(int i=1;i<n+1;i++){
    			for(int j=1;j<=v;j++){
    				if(j>=w[i]){
    					/*
    					 * 当能放得下这个物品时,放下这个物品,价值增加,但是空间减小,最大价值是dp[i-1][j-w[i]]+p[i]
    					 * 当不放这个物品时,空间大,物品还是到i-1,最大价值是dp[i-1][j]
    					 * 比较这两个大小,取最大的,就是dp[i][j]
    					 */
    					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
    				}else{
    					//如果放不下,就是放上一个物品时的dp
    					dp[i][j] = dp[i-1][j];
    				}
    			}
    		}
    		return dp[n][v];
    	}

    优化:滚动数组,只创建一个一维数组,长度为从1到W,初始值都是0,能装得下i时,dp[j] = Math.max(dp[j], dp[j-w[i]]+p[i]);装不下时,dp[j] = dp[j];

    public static int PackageHelper2(int n,int w[],int p[],int v) {
    		//设置一个二维数组,横坐标代表从第一个物品开始放到第几个物品,纵坐标代表背包还有多少容量,dp代表最大价值
    		int dp[] = new int[v+1];
    		for(int i=1;i<=n;i++){
    			for(int j=v;j>0;j--){
    				if(j>w[i]){
    					dp[j] = Math.max(dp[j], dp[j-w[i]]+p[i]);
    				}else{
    					dp[j] = dp[j];
    				}
    			}
    		}
    		return dp[v];
    	}

    7、找零钱问题:有几种方法

    具体思路同背包问题,这里只分析一下动态转化方程,能用这种零钱,分为用了这种零钱的方法跟没用到这种零钱的方法,dp[i][j] = dp[i-1][j] + dp[i][j-num[i]];如果不能用这种零钱,即所组成的面额小于当前零钱,直接等于不用这种零钱的数值,dp[i][j] = dp[i-1][j]。这里要特别注意的是。1、开始填写二维数组边界值时,第一行是填写只用第一种面额零钱组成相应数额的方法,要注意是总数额除以第一种面额取余为0才能组成,即如果第一种面额为2,不能组成3,5的数额等;2、填写二维数组第一列时,代表到用到面额为i时,剩余数额为0,即只用i就可以组成相应数额,这也是一种方法,所以第一列的值,第一个为0,后面全为1.

    public static int SmallMoney(int num[],int target) {
    		int m = num.length;
    		int dp[][] = new int[m][target+1];
    		dp[0][0] = 1;
    		for(int i=1;i<=target;i++){
    			if(i%num[0] == 0){
    				dp[0][i] = 1;//第一行数值填写
    			}else{
    				dp[0][i] = 0;
    			}
    		}
    		for(int i=0;i<m;i++){
    			dp[i][0] = 1;//第一列数值填写
    		}
    		for(int i=1;i<m;i++){
    			for(int j=1;j<=target;j++){
    				if(j<num[i]){
    					dp[i][j] = dp[i-1][j];
    				}else{
    					dp[i][j] = dp[i-1][j] + dp[i][j-num[i]];
    				}
    			}
    		}
    		return dp[m-1][target];
    	}

    优化:动态数组,同背包问题即以上分析。

    public static int SmallMoney2(int num[],int target) {
    		int m = num.length;
    		int dp[] = new int[target+1];
    		dp[0] = 1;
    		for(int i=1;i<=target;i++){
    			if(i%num[0] == 0){
    				dp[i] = 1;
    			}else{
    				dp[i] = 0;
    			}
    		}
    		for(int i=1;i<m;i++){
    			for(int j=1;j<=target;j++){
    				if(j>=num[i]){
    					dp[j] = dp[j] + dp[j-num[i]];
    				}
    			}
    		}
    		return dp[target];
    	}

    8、找零钱问题:所用面额数量最少

    跟上面思路相同,代码不同点:1、填写边界值时,第一行仍是看取余是不是为0,如果为0,填的是除以它的商,即用了几张。2、填写边界值第一列时,  第一列代表用了这一面额的纸币且剩下的数额为0,代表值用着一种纸币就可以构成这种数额,用的张数应该填到(i,j)处,所以第一列都是0;3、写状态转化方程时,要注意判断,如果数额小于面额,直接等于上一层值,dp[i][j]=dp[i-1][j];  如果数额等于面额,直接等于1;如果数额大于面额,先判断当用掉一张面额时,使用当前面额的剩余数额处是否有值,和不使用当前面额的剩余数额处是否有值,即当dp[i-1][j]!=0&&dp[i][j-num[i]]!=0即这两处都有值,就看那一个更小,如果不都有,仅仅选择一个有值的就好了,具体见代码:
    public static int SmallMoney(int num[],int target) {
    		int m = num.length;
    		int dp[][] = new int[m][target+1];
    		dp[0][0] = 0;
    		for(int i=1;i<=target;i++){
    			if(i%num[0] == 0){
    				dp[0][i] = i/num[0];//填入的是张数
    			}else{
    				dp[0][i] = 0;
    			}
    		}
    		for(int i=1;i<m;i++){
    			dp[i][0] = 0;//第一列应该为0
    		}
    		for(int i=1;i<m;i++){
    			for(int j=1;j<=target;j++){
    				if(j<num[i]){
    					dp[i][j] = dp[i-1][j];
    				}else if(j == num[i]){
    					dp[i][j] = 1;
    				}else{
    					if(dp[i-1][j]!=0&&dp[i][j-num[i]]!=0){//当两处都有值,即两种方法都可以组成当前数额,取用的张数更小的
    						dp[i][j] = Math.min(dp[i-1][j], dp[i][j-num[i]]+1);
    					}else{//如果不能,取能组成的就好
    						dp[i][j] = dp[i-1][j]!=0?dp[i-1][j]:dp[i][j-num[i]];
    					}
    				}
    			}
    		}
    		return dp[m-1][target];
    	}

    优化:滚动数组,具体思路一样

    public static int SmallMoney2(int num[],int target) {
    		int m = num.length;
    		int dp[] = new int[target+1];
    		dp[0] = 0;
    		for(int i=1;i<=target;i++){
    			if(i%num[0] == 0){
    				dp[i] = i/num[0];
    			}else{
    				dp[i] = 0;
    			}
    		}
    		for(int i=1;i<m;i++){
    			for(int j=1;j<=target;j++){
    				if(j<num[i]){
    					dp[j] = dp[j];
    				}else if(j == num[i]){
    					dp[j] = 1;
    				}else{
    					if(dp[j]!=0&&dp[j-num[i]]!=0){
    						dp[j] = Math.min(dp[j], dp[j-num[i]]+1);
    					}else{
    						dp[j] = dp[j]!=0?dp[j]:dp[j-num[i]];
    					}
    				}
    			}
    		}
    		return dp[target];
    	}

    动态规划和分治区别:

    动态规划算法:它通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。

    分治法:若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。

    总结:

    不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。


    展开全文
  • 非常好的动态规划总结,DP总结

    万次阅读 多人点赞 2017-06-22 09:31:18
    总结的非常好,谢谢作者。 http://cppblog.com/menjitianya/archive/2015/10/23/212084.html 目录 一、动态规划初探  1、递推  2、记忆化搜索  3、状态和状态转移 ...二、动态规划的经典


    总结的非常好,谢谢作者。

    http://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 <=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。
         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行。
    图二-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个骨牌的条件有如下几个:
           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行全铺满这个条件了,如图二-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,其它量都不变即可,这表示了这个格子什么都不放的情况。

          5、树状模型
          树形动态规划(树形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(nt
    ),每个子问题需要用到
    O(ne
    )个子问题的结果,那么我们称它为
    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】都是这类方程。
           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(nt+e
    )
    ,空间复杂度是O(nt
    )
    的算法,大多数情况下空间复杂度是很容易优化的,难点在于时间复杂度,下一章我们将详细讲解各种情况下的动态规划优化算法。

    四、动态规划和数据结构结合的常用优化
           1、滚动数组
          【例题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(n2),利用滚动数组可以将空间降掉一维,变成O(n)。
           背包问题的几个状态转移方程同样可以用滚动数组进行空间优化。

            
    2、最长单调子序列
           
    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(n2),利用单调性优化后可以将复杂度将至O(nlogn)。

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

           
    3、矩阵优化
          
    【例题15】三个小岛,编号1、2、3,老王第0天在1号岛上。这些岛有一些奇怪的规则,每过1天,1号岛上的人必须进入2、3号岛;2号岛上的人必须进入1号岛;3号岛上的人可以前往1、2或留在3号岛
    。问第n(n <=
    109
    )天老王在到达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岛的方案数,利用矩阵的传递性,
    A2的第i行的第j列则表示经过2天,从i岛到j岛的方案数,同样的,
    An 
    则表示了经过n天,从i岛到j岛的方案数,那么问题就转化成了求An 
    MOD 100000007的值了。
           
    An
    当n为偶数的时候等于(
    An/2
    )*(A
    n/2
    );当n为奇数的时候,等于(
    An/2
    )*
    (
    An/2)*A,这样求解矩阵
    An就可以在O(logn)的时间内完成了,加法和乘法对MOD操作都是可交换的(即 “先加再模” 和 “先模再加再模” 等价),所以可以在矩阵乘法求解的时候,一旦超出模数,就执行取模操作。
           最后求得的矩阵T = 
    AMOD 
    100000007,那么T[1][1]就是我们要求的解了。
           
    4、斜率优化
           【例题16】
    n(n <= 500000)个单词,每个单词输出的花费为Ci(1 <= i <= n),将k个连续的单词输出在一行的花费为:
           其中M为常数,求一个最佳方案,使得输出所有单词总的花费最小。
           令d[i]为前i个单词组织出的最小花费,s[i] = sum{Ck | 0 <= k <= i },其中s[0] = 0
           状态转移方程 d[i] = min{ d[j] + (s[i] - s[j])
    + M | 0 <= j < i }   (1 <= i <= n)
           这是个1D/1D问题,空间复杂度O(n), 时间复杂度为O(n
    2
    ),对于500000的数据来说是不可能在给定时间出解的。
           令g[j] = d[j] + (s[i] - s[j])
    2+ M,表示由 j 到 i 的决策。
           对于两个决策点 j < k,如果k的决策值小于j (即g[k] < g[j]),则有:
           d[k] + (s[i] - s[k]) 
    2 
    + M < d[j] + (s[i] - s[j])
    2
    + M
    ,然后将左边转化成关于j和k的表达式,右边转化成只有i的表达式。
           (中间省略t行推导过程...,t >= 5)
           (d[j] - d[k] + s[j]
    2
    - s[k]
    2
    ) / (s[j] - s[k]) < 2*s[i]
           令xj = d[j] + s[j]
    2
    ,   yj = s[j],则原式转化成: (xj - xk) / (yj - yk) < 2*s[i]
           不等式左边是个斜率的形式,我们用斜率函数来表示 slope(j, k) = (xj - xk) / (yj - yk)
           那么这里我们可以得出两个结论:
           1、当两个决策j、k (j < k)满足 slope(j, k) < 2*s[i]时,j决策是个无用决策,并且因为s[i]是个单调不降的,所以对于i < i',则有slope(j, k) < 2*s[i] < 2*s[i'],即j决策在随着i增大的过程中也是一直都用不到的。
           2、对于当前需要计算的值f[i],存在三个决策j、k、l,并且有 j < k < l,如果slope(j, k) > slope(k, l),则k这个决策是个无用决策,证明需要分情况讨论:
                 i. slope(k, l) < 2*s[i],则l的决策比k更优;
                 ii. slope(k, l) >= 2*s[i],则 slope(j, k) > slope(k, l) >= 2*s[i],j的决策比k更优;
                 综上所述,当slope(j, k) > slope(k, l)时,k是无用决策;
           那么可以用单调队列来维护一个决策队列的单调性,单调队列存的是决策序列。
           一开始队列里只有一个决策,就是0这个点(虚拟出的初始决策),根据第一个结论,如果队列里面决策数目大于1,则判断slope( Q[front], Q[front+1] ) < 2*s[i]是否成立,如果成立,Q[front]是个无用决策,front ++,如果不成立那么Q[front]必定是当前i的最优决策,通过状态转移方程计算f[i]的值,然后再根据第二个结论,判断slope(Q[rear-2], Q[rear-1]) > slope(Q[rear-1], i)是否成立,如果成立,那么Q[rear-1]必定是个无用决策,rear --,如果不成立,则将 i 作为当前决策 插入到队列尾, 即 Q[rear++] = i。
           这题需要注意,斜率计算的时候,分母有可能为0的情况。
     
          
    5、树状数组优化
           
    树状数组是一种数据结构,它支持两种操作:
           
    1、对点更新,即在给你(x, v)的情况下,在下标x的位置累加一个和v(耗时  O(log(n)) )。
                函数表示   void add(x, v);
           
    2、成端求和,给定一段区间[x, y],求区间内数据的和(这些数据就是第一个操作累加的数据,耗时
    O(log(n))
    )。
                函数表示   int sum(x, y);
           
    用其它数据结构也是可以实现上述操作的,例如线段树(可以认为它是一种轻量级的线段树,但是线段树能解决的问题更加普遍,而树状数组只能处理求和问题),但是树状数组的实现方便、
    常数
    复杂度低,使得它在解决对点更新成端求和问题上成为首选。这里并不会讲它的具体实现,有兴趣请参见
    树状数组
           【例题17】给定一个n
    (n <= 100000)个元素的序列a[i] (1 <= a[i] <= INF),定义"和谐序列"为序列的任何两个相邻元素相差不超过K,求a[i]的子序列中,"和谐序列"的个数 MOD 10000007。

           用d[i]表示以第i个元素结尾的"和谐序列"的个数, 令d[0] = 1, 那么sum {d[i] | 1 <= i <= n}就是我们要求的解。列出状态转移方程:
           d[i] = sum{ d[j] | j==0 || j < i && abs(a[i] - a[j]) <= K }
           这是一个1D/1D问题,如果不进行任何优化,时间复杂度是O(n^2
    )。
           我们首先假设K是个无限大的数,也就是不考虑abs(a[i] - a[j]) <= K这个限制,那这个问题要怎么做?很显然d[1] = 1,d[2] = 1 + d[1],d[3] = d[1] + d[2] + 1(这里的1其实是状态转移方程中j == 0的情况,也就是只有一个数a[i]的情况),更加一般地:
           d[i] = sum{d[j] | j < i} + 1
           对于这一步状态转移还是O(n)的,但是我们可以将它稍加变形,如下:
           d[i] = sum(1, INF) + 1;               (这里的sum是树状数组的区间求和函数) 
           得到d[i]的值后,再将d[i]插入到树状数组中,利用树状数组第1条操作 add(a[i], d[i]);
           基于这样的一种思路,我们发现即使有了限制K,同样也是可以求解的,只是在求和的时候进行如下操作:
           d[i] = sum(a[i] - K, a[i] + K) + 1;
          这样就把原本O(n)的状态转移变成了 O(logn),整个算法时间复杂度O(logn)。
     
           
    6、线段树优化
           线段树
    是一种完全二叉树,它支持区间求和、区间最值等一系列区间问题,这里为了将问题简化,直接给出求值函数而暂时不去讨论它的具体实现,有兴趣的可以自行寻找资料。线段树可以扩展到二维,二维线段树是一棵四叉树,一般用于解决平面统计问题,参见
    二维线段树
           
    这里给出线段树的求区间最值需要用到的函数,即:
           
    1、insert(x, v)            在下标为x的位置插入一个值v;  耗时 O( log(n) )
           
    2、query(l, r)             求下标在[l, r]上的最值;             耗时 O( log(n) )
           【例题18】详见 例题13
           
    还是以最长单调子序列为例,状态转移方程为:
           
    d[i] = max{ d[j] | j < i && a[j] < a[i] } + 1
           这里我们首先要保证 1 <= a[i] <= n,如果a[i]是实数域的话,首先要对a[i]进行离散化,排序后从小到大重新编号,最小的a[i]编号为1,最大的a[i]编号为n。
           对于状态转移执行线段树的询问操作: d[i] = query( 1, a[i] - 1 ) + 1
           然后再执行插入操作: insert( a[i], d[i] )
           状态转移同样耗时O(logn)。
           这个思想和树状数组的思想很像,大体思路都是将数本身映射到某个数据结构的下标。

           7、其他优化
           a.散列HASH状态表示
           b.结合数论优化
           c.结合计算几何优化
           d.四边形不等式优化
           e.等等

    五、动态规划题集整理

      1、递推

            Recursion Practice                              ★☆☆☆☆          几个初级递推
            Put Apple                                       ★☆☆☆☆

            Tri Tiling                                      ★☆☆☆☆          【例题1】
            Computer Transformation                         ★☆☆☆☆          【例题2】
            Train Problem II                                ★☆☆☆☆          
            How Many Trees?                                 ★☆☆☆☆          
            Buy the Ticket                                  ★☆☆☆☆          
            Game of Connections                             ★☆☆☆☆
            Count the Trees                                 ★☆☆☆☆
            Circle                                          ★☆☆☆☆
            Combinations, Once Again                        ★★☆☆☆
            Closing Ceremony of Sunny Cup                   ★★☆☆☆           
            Rooted Trees Problem                            ★★☆☆☆          
            Water Treatment Plants                          ★★☆☆☆           
            One Person                                      ★★☆☆☆
            Relax! It’s just a game                        ★★☆☆☆
            N Knight                                        ★★★☆☆
            Connected Graph                                 ★★★★★          楼天城“男人八题”之一


       2、记忆化搜索

            Function Run Fun                                ★☆☆☆☆          【例题3】

            FatMouse and Cheese                             ★☆☆☆☆          经典迷宫问题

            Cheapest Palindrome                             ★★☆☆☆ 

            A Mini Locomotive                               ★★☆☆☆

            Millenium Leapcow                               ★★☆☆☆

            Brackets Sequence                               ★★★☆☆          经典记忆化

            Chessboard Cutting                              ★★★☆☆          《算法艺术和信息学竞赛》例题

            Number Cutting Game                             ★★★☆☆


       3、最长单调子序列

            Constructing Roads In JG Kingdom                ★★☆☆☆

            Stock Exchange                                  ★★☆☆☆

            Wooden Sticks                                   ★★☆☆☆

            Bridging signals                                ★★☆☆☆

            BUY LOW, BUY LOWER                              ★★☆☆☆         要求需要输出方案数

            Longest Ordered Subsequence                     ★★☆☆☆

            Crossed Matchings                               ★★☆☆☆

            Jack's struggle                                 ★★★☆☆          稍微做点转化


       4、最大M子段和

            Max Sum                                         ★☆☆☆☆              最大子段和

            Max Sum Plus Plus                               ★★☆☆☆              最大M子段和

            To The Max                                      ★★☆☆☆              最大子矩阵

            Max Sequence                                    ★★☆☆☆              最大2子段和

            Maximum sum                                     ★★☆☆☆              最大2子段和

            最大连续子序列                                  ★★☆☆☆              最大子段和

            Largest Rectangle in a Histogram                ★★☆☆☆              最大子矩阵变形

            City Game                                       ★★☆☆☆              最大子矩阵扩展

            Matrix Swapping II                              ★★★☆☆              最大子矩阵变形后扩展


       5、线性模型

            Skiing                                          ★☆☆☆☆

            Super Jumping! Jumping! Jumping!                ★☆☆☆☆ 

            Milking Time                                    ★★☆☆☆         区间问题的线性模型

            Computers                                       ★★☆☆☆         【例题5】

            Bridge over a rough river                       ★★★☆☆         【例题6】

            Crossing River                                  ★★★☆☆         【例题6】大数据版

            Blocks                                          ★★★☆☆          

            Parallel Expectations                           ★★★★☆         线性模型黑书案例

           6、区间模型

            Palindrome                                      ★☆☆☆☆         【例题7】

            See Palindrome Again                            ★★★☆☆


           7、背包模型

            饭卡                                            ★☆☆☆☆              01背包

            I NEED A OFFER!                                 ★☆☆☆☆              概率转化

            Bone Collector                                  ★☆☆☆☆              01背包

            最大报销额                                      ★☆☆☆☆              01背包

            Duty Free Shop                                  ★★☆☆☆              01背包

            Robberies                                       ★★☆☆☆              【例题8】 

            Piggy-Bank                                      ★☆☆☆☆              完全背包

            Cash Machine                                    ★☆☆☆☆              多重背包

            Coins                                           ★★☆☆☆              多重背包,楼天城“男人八题”之一

            I love sneakers!                                ★★★☆☆              背包变形

           8、状态压缩模型

            ChessboardProblem                               ★☆☆☆☆              比较基础的状态压缩

            Number of Locks                                 ★☆☆☆☆              简单状态压缩问题

            Islands and Bridges                             ★★☆☆☆              【例题9】

            Tiling a Grid With Dominoes                     ★★☆☆☆              骨牌铺方格 4XN的情况

            Mondriaan's Dream                               ★★☆☆☆              【例题10】的简易版

            Renovation Problem                              ★★☆☆☆              简单摆放问题

            The Number of set                               ★★☆☆☆

            Hardwood floor                                  ★★★☆☆              【例题10】二进制状态压缩鼻祖

            Tetris Comes Back                               ★★★☆☆              纸老虎题

            Bugs Integrated, Inc.                           ★★★☆☆              三进制状态压缩鼻祖

            Another Chocolate Maniac                        ★★★☆☆              三进制

            Emplacement                                     ★★★☆☆              类似Bugs那题,三进制

            Toy bricks                                      ★★★☆☆              四进制, 左移运算高于&

            Quad Tiling                                     ★★★☆☆              骨牌铺方格 4XN的情况 利用矩阵优化

            Eat the Trees                                   ★★★☆☆              插头DP入门题

            Formula 1                                       ★★★☆☆              插头DP入门题

            The Hive II                                     ★★★☆☆              插头DP

            Plan                                            ★★★☆☆              插头DP

            Manhattan Wiring                                ★★★☆☆              插头DP

            Pandora adventure                               ★★★★☆              插头DP

            Tony's Tour                                     ★★★★☆              插头DP,楼天城“男人八题”之一

            Pipes                                           ★★★★☆              插头DP

            circuits                                        ★★★★☆              插头DP

            Beautiful Meadow                                ★★★★☆              插头DP

            I-country                                       ★★★★☆              高维状态表示

            Permutaion                                      ★★★★☆              牛逼的状态表示

            01-K Code                                       ★★★★☆

            Tour in the Castle                              ★★★★★              插头DP(难)

            The Floor Bricks                                ★★★★★              四进制(需要优化)

           9、树状模型

            Anniversary party                               ★☆☆☆☆              树形DP入门

            Strategic game                                  ★☆☆☆☆              树形DP入门

            Computer                                        ★★☆☆☆ 

            Long Live the Queen                             ★★☆☆☆

            最优连通子集                                    ★★☆☆☆ 

            Computer Network                                ★★☆☆☆

            Rebuilding Roads                                ★★★☆☆              树形DP+背包

            New Year Bonus Grant                            ★★★☆☆

            How Many Paths Are There                        ★★★☆☆  

            Intermediate Rounds for Multicast               ★★★★☆

            Fire                                            ★★★★☆

            Walking Race                                    ★★★★☆

            Tree                                            ★★★★★              树形DP,楼天城“男人八题”之一

       
            10、滚动数组优化常见问题

            Palindrome                                      ★☆☆☆☆

            Telephone Wire                                  ★☆☆☆☆

            Gangsters                                       ★☆☆☆☆

            Dominoes                                        ★☆☆☆☆

            Cow Exhibition                                  ★☆☆☆☆

            Supermarket                                     ★★☆☆☆
     

            11、决策单调性

            Print Article                                   ★★★☆☆

            Lawrence                                        ★★★☆☆

            Batch Scheduling                                ★★★☆☆

            K-Anonymous Sequence                            ★★★☆☆

            Cut the Sequence                                ★★★☆☆

            12、常用优化

            Divisibility                                    ★★☆☆☆        利用同余性质

            Magic Multiplying Machine                       ★★☆☆☆        利用同余性质

            Moving Computer                                 ★★☆☆☆        散列HASH表示状态

            Post Office                                     ★★★☆☆        四边形不等式

            Minimizing maximizer                            ★★★☆☆        线段树优化

            Man Down                                        ★★★☆☆        线段树优化

            So you want to be a 2n-aire?                    ★★★☆☆        期望问题

            Expected Allowance                              ★★★☆☆        期望问题

            Greatest Common Increase Subseq                 ★★★☆☆        二维线段树优化

            Traversal                                       ★★★☆☆        树状数组优化

            Find the nondecreasing subsequences             ★★★☆☆        树状数组优化

            Not Too Convex Hull                             ★★★★☆        利用凸包进行状态转移

            In Action                                       ★★★☆☆        最短路+背包

            Search of Concatenated Strings                  ★★★☆☆        STL bitset 应用

            13、其他类型的动态规划

            Common Subsequence                              2D/0D

            Advanced Fruits                                 2D/0D

            Travel                                          2D/1D

            RIPOFF                                          2D/1D

            Balls                                           2D/1D

            Projects                                        2D/1D

            Cow Roller Coaster                              2D/1D 

            LITTLE SHOP OF FLOWERS                          2D/1D

            Pearls                                          2D/1D

            Spiderman                                       2D/0D

            The Triangle                        2D/0D 

            Triangles                           2D/0D

            Magazine Delivery                     3D/0D

            Tourist                             3D/0D

            Rectangle                           2D/1D

            Message                             2D/1D

            Bigger is Better                      2D/1D

            Girl Friend II                       2D/1D

            Phalanx                             2D/1D

            Spiderman                           最坏复杂度O(NK),K最大为1000000,呵呵

            Find a path                                     3D/1D 公式简化,N维不能解决的问题试着用N+1维来求解


    展开全文
  • 动态规划系列(1)——动态规划入门

    千次阅读 多人点赞 2018-08-01 16:47:32
    一般的,我们常用的解决问题的方法有暴力解决法、分而治之、二分法、贪心法和动态规划法。在你遇到一个问题怎么想都想不出其解法的时候,很可能就需要用到动态规划了;在你的题目中出现最优、最多、最好等字眼的时候...
  • 动态规划

    千次阅读 2018-08-16 23:01:22
    动态规划的实质是分治思想和解决冗余,因此动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,已解决最优化问题的算法策略。由此可知,动态规划法与分治法和贪心法类似...
  • 动态规划入门(超详细整理)

    千次阅读 多人点赞 2018-08-07 21:03:29
    看故事了解动态规划思想:click here!!! 求解动态规划问题求到最后无非就三种方法,见我之前的博文用三中方法详细讲解了01背包问题。 第一种递归搜索法:...
  • 动态规划

    千次阅读 2016-05-25 23:31:47
    遍历做法int dfs(int n,int sum){ int res; if(n==k+1) return 0; res=max(dfs(n+1,sum+a[2*n]),dfs(n+1,sum+a[2*n+1])); ret
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 问题描述 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8 ...
  • 动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答案,但就是自己不会做,不知道怎么下手。就像做...
  • 动态规划之01背包问题(最易理解的讲解)

    万次阅读 多人点赞 2012-07-06 17:09:37
    01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi...
  • 动态规划

    千次阅读 多人点赞 2019-06-30 21:30:12
    动态规划
  • 动态规划!!!动态规划!!!

    千次阅读 多人点赞 2017-08-03 10:35:42
    动态规划
  • 最火的瓜,得用动态规划来吃

    万次阅读 多人点赞 2020-04-23 21:45:46
    罗志祥才是动态规划的高手一、事件的前因后果二、被罗志祥的技术能力折服三、 你要成为这样的高手吗?四、 递归树分析五、 动态规划的代码六、 与妹子沟通是个技术活 今天真是被罗志祥的大瓜砸到了!全网络都是关于...
  • 动态规划

    千次阅读 2019-04-30 07:16:39
    1 引言 1.1 动态规划的发展及研究内容 例 1 最短路线问题 例 2 生产计划问题 2 基本概念、基本方程和计算方法 2.1 动态规划的基本概念和基本方程 2.1.1 阶段 2.1.2 状态 2.1.3 决策 ...
  • 文章目录1.序2.动态规划的基本概念[^1]3.动态规划算法的基本思想[^2]4....这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...
  • 总结——01背包问题 (动态规划算法)

    万次阅读 多人点赞 2017-04-25 20:57:57
    0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。 问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?
  • 动态规划 最长公共子序列 过程图解

    万次阅读 多人点赞 2016-05-29 22:54:25
    1.基本概念  首先需要科普一下,最长公共子序列(longest common sequence)和最长公共子串(longest common substring)不是一回事儿。什么是子序列呢?即一个给定的序列的子序列,就是将给定序列中零个或多个...

空空如也

1 2 3 4 5 ... 20
收藏数 308,681
精华内容 123,472
关键字:

动态规划