动态规划算法 订阅
动态规划(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]  。
收起全文
精华内容
下载资源
问答
  • 动态规划算法

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

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

        首先,我们看一下这道题(此题目来源于北大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行的三角形,我们可以写出如下的递归式:   

    [cpp] view plain copy
    1. if ( r == N)                  
    2.     MaxSum(r,j) = D(r,j)    
    3. else        
    4.     MaxSum( r, j) = Max{ MaxSum(r+1,j), MaxSum(r+1,j+1) } + D(r,j)   

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

    [cpp] view plain copy
    1. #include <iostream>    
    2. #include <algorithm>   
    3. #define MAX 101    
    4. using namespace std;   
    5. int D[MAX][MAX];    
    6. int n;    
    7. int MaxSum(int i, int j){      
    8.     if(i==n)    
    9.         return D[i][j];      
    10.     int x = MaxSum(i+1,j);      
    11.     int y = MaxSum(i+1,j+1);      
    12.     return max(x,y)+D[i][j];    
    13. }  
    14. int main(){      
    15.     int i,j;      
    16.     cin >> n;      
    17.     for(i=1;i<=n;i++)     
    18.         for(j=1;j<=i;j++)          
    19.             cin >> D[i][j];      
    20.     cout << MaxSum(1,1) << endl;    
    21. }        

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

        

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

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

        

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

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

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

    [cpp] view plain copy
    1. #include <iostream>    
    2. #include <algorithm>   
    3. using namespace std;  
    4.    
    5. #define MAX 101  
    6.     
    7. int D[MAX][MAX];      
    8. int n;    
    9. int maxSum[MAX][MAX];  
    10.    
    11. int MaxSum(int i, int j){        
    12.     if( maxSum[i][j] != -1 )           
    13.         return maxSum[i][j];        
    14.     if(i==n)     
    15.         maxSum[i][j] = D[i][j];       
    16.     else{      
    17.         int x = MaxSum(i+1,j);         
    18.         int y = MaxSum(i+1,j+1);         
    19.         maxSum[i][j] = max(x,y)+ D[i][j];       
    20.     }       
    21.     return maxSum[i][j];   
    22. }   
    23. int main(){      
    24.     int i,j;      
    25.     cin >> n;      
    26.     for(i=1;i<=n;i++)     
    27.         for(j=1;j<=i;j++) {         
    28.             cin >> D[i][j];         
    29.             maxSum[i][j] = -1;     
    30.         }      
    31.     cout << MaxSum(1,1) << endl;   
    32. }   

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

        

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

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

        

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

        

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

        

        

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

    [cpp] view plain copy
    1. #include <iostream>    
    2. #include <algorithm>   
    3. using namespace std;   
    4.   
    5. #define MAX 101    
    6.   
    7. int D[MAX][MAX];     
    8. int n;    
    9. int maxSum[MAX][MAX];   
    10. int main(){      
    11.     int i,j;      
    12.     cin >> n;      
    13.     for(i=1;i<=n;i++)     
    14.         for(j=1;j<=i;j++)          
    15.             cin >> D[i][j];     
    16.     forint i = 1;i <= n; ++ i )       
    17.         maxSum[n][i] = D[n][i];     
    18.     forint i = n-1; i>= 1;  --i )       
    19.         forint j = 1; j <= i; ++j )           
    20.             maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];      
    21.     cout << maxSum[1][1] << endl;    
    22. }   

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

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

        

        

        

        

        

        

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

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

    [cpp] view plain copy
    1. #include <iostream>    
    2. #include <algorithm>   
    3. using namespace std;   
    4.   
    5. #define MAX 101    
    6.   
    7. int D[MAX][MAX];    
    8. int n;   
    9. int * maxSum;   
    10.   
    11. int main(){      
    12.     int i,j;      
    13.     cin >> n;      
    14.     for(i=1;i<=n;i++)     
    15.         for(j=1;j<=i;j++)          
    16.             cin >> D[i][j];     
    17.     maxSum = D[n]; //maxSum指向第n行      
    18.     forint i = n-1; i>= 1;  --i )       
    19.         forint j = 1; j <= i; ++j )         
    20.             maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j];      
    21.     cout << maxSum[1] << endl;    
    22. }  

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

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

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

        动规解题的一般思路

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

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

        2.确定状态

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

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

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

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

        4. 确定状态转移方程

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

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

        
      

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

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

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

    
    展开全文
  • 剑指Offer——动态规划算法

    万次阅读 多人点赞 2016-08-03 15:24:27
    剑指Offer——动态规划算法什么是动态规划? 和分治法一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。 分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解...

    剑指Offer——动态规划算法

    什么是动态规划?

         和分治法一样,动态规划(dynamic programming)是通过组合子问题而解决整个问题的解。

         分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。

         动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。

         此时,分治法会做许多不必要的工作,即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次,将其结果保存起来,从而避免每次遇到各个子问题时重新计算答案。

    适用范围

         最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时,则称该问题具有最优子结构特性。

         最优性原理是动态规划的基础。任何一个问题,如果失去了这个最优性原理的支持,就不可能用动态规划设计求解。

         1.问题中的状态满足最优性原理。

         2.问题中的状态必须满足无后效性。

         所谓无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前状态是对以往决策的总结”。

    动态规划算法的设计

         两种方法:

         自顶向下(又称记忆化搜索、备忘录):基本上对应着递归函数实现,从大范围开始计算,要注意不断保存中间结果,避免重复计算

         自底向上(递推):从小范围递推计算到大范围

    动态规划的重点

        递归方程+边界条件

    爬楼梯问题

         一个人每次只能走一层楼梯或者两层楼梯,问走到第80层楼梯一共有多少种方法。

         设DP[i]为走到第i层一共有多少种方法,那么DP[80]即为所求。很显然DP[1]=1, DP[2]=2(走到第一层只有一种方法:就是走一层楼梯;走到第二层有两种方法:走两次一层楼梯或者走一次两层楼梯)。同理,走到第i层楼梯,可以从i-1层走一层,或者从i-2走两层。很容易得到:

          递推公式:DP[i]=DP[i-1]+DP[i-2]

          边界条件:DP[1]=1   DP[2]=2

          (a)自顶向下的解法:

     

    long long dp[81] = {0};/*用于保存中间结果否则会重复计算很多重复的子问题*/
    long long DP(int n)
    {
        if(dp[n])
            return dp[n];
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        dp[n] = DP(n-1) + DP(n-2);
        return dp[n];
    }  

     

         (b)自底向上的解法:

     

    int i;  
    long long dp[81]; /* 注意当n超过75时,结果值将超过int范围 */  
    dp[1] = 1;  
    dp[2] = 2;  
    for(i=3; i <= 80; i++)  
        dp[i] = dp[i-1] + dp[i-2];

     

    最长上升子序列

         对于序列:4 1 2 24,它的最长上升子序列是1 2 4,长度为3。

         对于序列:4 2 4 25 6,它的最长上升子序列是2 4 5 6,长度为4。

         设a[i]表示原序列,设DP[i]表示以第i个数结尾的最长上升序列的长度,那么很显然想导出DP[i]的值,需要在DP[k](1<=k<i)中找出满足a[k]<a[i]最大的一项。假设第kk项是我们找到的答案,那么第i个数就可以接在第kk个数之后,成为以第i个数结尾的最长升序列。如果没有找到答案,换言之第i个数比前面的数都要小,那么DP[i]=1,也即生成了从自己开始又以自己结尾的最长升序列。综上,我们很容易得出:

         递推公式:DP[i]=max(DP[k]+1,DP[i])  1<=k<i

         边界条件:DP[i]=1                   1<=i<=n

         算法复杂度为O(n^2)

     

    void RiseSequence(int Array[], int num)  
    {  
    #define MAX_LENGTH  30  
        struct  
        {  
            int SequenceValue;  /* max length ending with this num */  
            int PreviousIndex;  /* record the previous number */  
        }ArrayInfo[MAX_LENGTH], temp;  
        int i;  
        for(i = 0; i < num; i++)  
        {  
            int j;  
            ArrayInfo[i].SequenceValue = 1;  
            ArrayInfo[i].PreviousIndex = -1;  
            for(j = 0; j < i; j++)  
            {  
                if(Array[j] < Array[i] && (ArrayInfo[j].SequenceValue + 1 > ArrayInfo[i].SequenceValue))  
                {  
                    ArrayInfo[i].SequenceValue = ArrayInfo[j].SequenceValue + 1;  
                    ArrayInfo[i].PreviousIndex = j;  
                }  
            }  
        }  
        temp.SequenceValue = ArrayInfo[0].SequenceValue;  
        for(i = 1; i < num; i++)  
        {  
            if(temp.SequenceValue < ArrayInfo[i].SequenceValue)  
            {  
                temp.SequenceValue = ArrayInfo[i].SequenceValue;  
                temp.PreviousIndex = i;  
            }  
        }  
        for(i = 0; i < temp.SequenceValue; i++)  
        {  
            printf("%d  ", Array[temp.PreviousIndex]);  /* in reverse order */  
            temp.PreviousIndex = ArrayInfo[temp.PreviousIndex].PreviousIndex;  
        }  
        printf("\nthe max rising sequence length is %d\n", temp.SequenceValue);  
    }  

     

    最长公共子序列

         给定两个序列X和Y,称序列Z是X和Y的公共子序列如果Z既是X的一个子序列,又是Y的一个子序列。例如,如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一个公共子序列,但是它并不是X和Y的最长公共子序列,因为它的长度为3。而同为X和Y公共子序列的{b,c,b,a},长度为4,因为找不到长度为5或更大的公共子序列,所以X和Y的最长公共子序列长度就为4。

         假设两个序列数组分别为a,b。定义f(i,j)为计算到a数组第i个数、b数组第j个数时所得到的最长公共子序列的长度。这时有两种情况:

         1.假如a[i]=b[j],那么f(i,j)=f(i-1,j-1)+1

         2.假如a[i]!=b[j],那么f(i,j)=max(f(i-1,j),f(i,j-1))

         边界条件为:f(i,0)=0     1<=i<=len(a)

                f(0,j)=0     1<=j<=len(b)

         算法复杂度:O(n^2),len(a)表示数组a的长度。

    尾声

         动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题,去设计状态转移方程式。

    动态规划还有很多变形,如状态压缩,树形等等。

        虽然通常我们用递归的方式分析动态规划问题,但最终都会基于循环去编码。

    美文美图

     

    展开全文
  • 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 什么是动态规划 动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题...

    动态规划(Dynamic programming)

    是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

     

    什么是动态规划

        动态规划(Dynamic Programming)对于子问题重叠的情况特别有效,因为它将子问题的解保存在表格中,当需要某个子问题的解时,直接取值即可,从而避免重复计算!

        动态规划是一种灵活的方法,不存在一种万能的动态规划算法可以解决各类最优化问题(每种算法都有它的缺陷)。所以除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,用灵活的方法建立数学模型,用创造性的技巧去求解。

     

    基本策略

        基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

        动态规划中的子问题往往不是相互独立的(即子问题重叠)。在求解的过程中,许多子问题的解被反复地使用。为了避免重复计算,动态规划算法采用了填表来保存子问题解的方法。

     

    适用问题

    那么什么样的问题适合用动态规划的方法来解决呢?

        适合用动态规划来解决的问题,都具有下面三个特点:最优化原理、无后效性、有重叠子问题

     

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

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

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

     

    这类问题的求解步骤通常如下:

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

    (1)划分:按照问题的特征,把问题分为若干阶段。注意:划分后的阶段一定是有序的或者可排序的

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

    (3)确定决策并写出状态转移方程:状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程

    (4)边界条件:状态转移方程是一个递推式,因此需要找到递推终止的条件

     

    算法实现

    动态规划三要素:

    (1)问题的阶段

    (2)每个阶段的状态

    (3)相邻两个阶段之间的递推关系

    整个求解过程可以用一张最优决策表来描述,最优决策表是一张二维表(行:决策阶段,列:问题的状态)表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

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

     

    1 事例一背包问题

    问题描述:假设我们有n种类型的物品,分别编号为1, 2...n。其中编号为i的物品价值为vi,它的重量为wi。为了简化问题,假定价值和重量都是整数值。现在,假设我们有一个背包,它能够承载的重量是Cap。现在,我们希望往包里装这些物品,使得包里装的物品价值最大化,那么我们该如何来选择装的东西呢?注意:每种物品只有一件,可以选择放或者不放。初始化数据为:n=5,w={2,2,6,5,4},v={6,3,5,4,6},Cap=10

    解法如下:

    A)描述最优解的结构

    设子问题:f[i][v]表示允许前i件物品放入容量为v的背包时可以获得的最大价值。注:这里的i从0到5,v从0到10

    为了能够得到已经计算过的,更小规模的子问题,我们可以根据当前限重来只考虑第i件物品放或者不放,那么就可以转化为涉及前i-1件物品的问题,

    即:

    情况1、如果第i件物品不能放(即这个物品的重量直接大于了当前限重v),则问题转化为“前i-1件物品放入容量为v的背包中”,即f[i-1][v];

    情况2、如果放第i件物品是可以放也可以不放,则问题转化为:

    1)、如果选择不放第i件物品,则问题转化为“前i-1件物品放入容量为v的背包中”,即变大时f[i-1][v];

    2)、如果选择放第i件物品,则问题转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”,此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。

    则情况2下,f[i][v]的值就是1),2)中最大的那个值。

    最优子结构描述如下:当子问题f[i][v]是最优时,其子问题f[i-1][v]和f[i-1][v-w[i]](中的较大者)显然同样也必须是最优的值,不然在情况1或者情况2下总会矛盾。

    B) 递归定义最优解的值

    根据上面的分析,显然子问题

    f[i][v]=f[i-1][v],这时是情况1

    f[i][v]=max{f[i-1][v], f[i-1][v-w[i]]+v[i] },这时是情况2。

    C)按自底而上的方式计算最优解的值

    import numpy as np
     
    #行李数n,不超过的重量W,重量列表w和价值列表p
    def fun(n,W,w,p):
    	a=np.array([[0]*(W+1)]*(n+1))
    	#依次计算前i个行李的最大价值,n+1在n的基础上进行
    	for i in range(1,n+1):
    		for j in range(1,W+1):
    			if w[i-1]>j:
    				a[i,j]=a[i-1,j]
    			else:
    				a[i,j]=max(a[i-1,j],p[i-1]+a[i-1,j-w[i-1]])#2种情况取最大值
    	#print(a)
    	print('max value is'+str(a[n,W]))
    	findDetail(p,n,a[n,W])
    #找到价值列表中的一个子集,使得其和等于前面求出的最大价值,即为选择方案
    def findDetail(p,n,v):
    	a=np.array([[True]*(v+1)]*(n+1))
    	for i in range(0,n+1):
    		a[i][0]=True
    	for i in range(1,v+1):
    		a[0][i]=False
    	for i in range(1,n+1):
    		for j in range(1,v+1):
    			if p[i-1]>j:
    				a[i,j]=a[i-1,j]
    			else:
    				a[i,j]=a[i-1,j] or a[i-1,j-p[i-1]]
    	if a[n,v]:
    		i=n
    		result=[]
    		while i>=0:
    			if a[i,v] and not a[i-1,v]:
    				result.append(p[i-1])
    				v-=p[i-1]
    			if v==0:
    				break
    			i-=1
    		print(result)
    	else:
    		print('error')
    weights=[1,2,5,6,7,9]
    price=[1,6,18,22,28,36]
    fun(len(weights),13,weights,price)

    2 事例二

    有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。

    分析:动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上,我们让f(n)表示走上n级台阶的方法数。

    那么当n为1时,f(n) = 1,n为2时,f(n) =2,就是说当台阶只有一级的时候,方法数是一种,台阶有两级的时候,方法数为2。那么当我们要走上n级台阶,必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步,所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2),我们用dp[n]来表示动态规划表,dp[i],i>0,i<=n,表示到达i级台阶的方法数。

    class Solution:
        """
        @param n: an integer
        @return: an ineger f(n)
        """
    
        def up(self, n):
            # write your code here
            # if n == 0:
            #     return 0
            L = []
            L.append(1)
            L.append(2)
            for i in range(2, n):
                L.append(L[i - 1] + L[i - 2])
            return L[n - 1]

    3 事例三

    给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有数字累加起来就是路径和,返回所有路径的最小路径和,如果给定的m如下,那么路径1,3,1,0,6,1,0就是最小路径和,返回12.

    1 3 5 9

    8 1 3 4

    5 0 6 1

    8 8 4 0

    分析:对于这个题目,假设m是m行n列的矩阵,那么我们用dp[m][n]来抽象这个问题,dp[i][j]表示的是从原点到i,j位置的最短路径和。我们首先计算第一行和第一列,直接累加即可,那么对于其他位置,要么是从它左边的位置达到,要么是从上边的位置达到,我们取左边和上边的较小值,然后加上当前的路径值,就是达到当前点的最短路径。然后从左到右,从上到下依次计算即可。

    m[i][j] = min(m[i-1][j],m[i][j-1]) + p[i][j]

    代码不再详细写,与背包问题类似的矩阵求解。

    4 事例四

    给定两个字符串str1和str2,返回两个字符串的最长公共子序列,例如:str1="1A2C3D4B56",str2="B1D23CA45B6A","123456"和"12C4B6"都是最长公共子序列,返回哪一个都行。

    分析:本题是非常经典的动态规划问题,假设str1的长度为M,str2的长度为N,则生成M*N的二维数组dp,dp[i][j]的含义是str1[0..i]与str2[0..j]的最长公共子序列的长度。

    dp值的求法如下:

    dp[i][j]的值必然和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]相关,结合下面的代码来看,我们实际上是从第1行和第1列开始计算的,而把第0行和第0列都初始化为0,这是为了后面的取最大值在代码实现上的方便,dp[i][j]取三者之间的最大值。

    # 此例中有多个相同长度的公共子串,但只能获取第一个子串
    def find_lcsubstr(s1, s2): 
    	# 下面4行不要直接写在循环中,减少计算
    	s1_len = len(s1) + 1 					#为方便后续计算,多了1行1列 
    	s2_len = len(s2) + 1
    	s3_len = len(s1)
    	s4_len = len(s2)
    	m = [[0 for j in range(s2_len)] for i in range(s1_len)] #生成0矩阵
    	maxNum = 0   							#初始最长匹配长度
    	p = 0  									#匹配的起始位置
    	for i in range(s3_len):
    		for j in range(s4_len):
    			if s1[i] == s2[j]:				  #相同则累加
    				m[i + 1][j + 1] = m[i][j] + 1 #给相同字符赋值,值为左上角值加1
    				if m[i + 1][j + 1] > maxNum:
    					maxNum = m[i + 1][j + 1]  #获取最大匹配长度
    					p = i + 1 				  #记录最大匹配长度的终止位置
    	print(m)
    	return s1[p - maxNum : p], maxNum   	  #返回最长子串及其长度
    print(find_lcsubstr(str_a, str_b))
    

    5 事例五

    把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

    解题思路:这个用动态规划感觉就很好啦

    终止条件:第N个丑数

    状态:s[i] 第i个丑数

    状态转移方程: s[i] = min(s[t1]*2 , s[t2]*3, s[t3]*5)。这个t1,t2,t3<i-1

    这3个t怎么确定呢?从i-1往后倒腾,满足s[t1-1]*2小于等于s[i-1]但s[t1]*2大于s[i-1]

    确定了之后敲代码把~~(代码还有很多可以优化的,但觉得这个可读性比较强,贴上自己的代码)
     

    class Solution:
        def GetUglyNumber_Solution(self, index):
            if index<1:
                return 0
            if index==1:
                return 1
            s = []
            s.append(1)
            t1 = 0
            t2 = 0
            t3 = 0
            for i in range(1,index):            
                for j in range(i):
                    if s[j]*2 > s[i-1]:
                        t1 = j
                        break
                for j in range(i):
                    if s[j]*3 > s[i-1]:
                        t2 = j
                        break
                for j in range(i):
                    if s[j]*5 > s[i-1]:
                        t3 = j   
                        break
                s.append(min(s[t1]*2,s[t2]*3,s[t3]*5))
                
            return s[-1]
    

    6 事例六

    找零钱问题,已经零钱面额为1、3、4,求找零n所用零钱数最少的方案

    解答过程:对于找零n的最少零钱数f(n),它和f(n-1),f(n-3),f(n-4)有关,即它等于这3者中最小的值加1.

    # 找零钱字典,key为面额,value为最少硬币数
    change_dict = {}
     
    def rec_change(M, coins):
        change_dict[0] = 0
        s = 0
     
        for money in range(1, M+1):
            num_of_coins = float('inf')
            #意思是要求50的最少找零数,在46,47,49的最少找零数中找到最小的即可
            for coin in coins:
                if money >= coin:
                    # 记录每次所用的硬币数量
                    if change_dict[money-coin]+1 < num_of_coins:
                        num_of_coins = change_dict[money-coin]+1
                        s = coin #记录每次找零的面额
     
            change_dict[money] = num_of_coins
        return change_dict[M],s
     
    # 求出具体的找零方式
    # 用path变量记录每次找零的面额
    def method(M, coins):
        print('Total denomination is %d.'%M)
        nums, path = rec_change(M, coins)#path为最少硬币数方案中的一个面额值
        print('The smallest number of coins is %d.'%nums)
        print('%s'%path, end='')
     
        while M-path > 0:
            M -= path
            nums, path = rec_change(M, coins)
            print(' -> %s'%path, end='')
        print()
     
    coins = (1, 3, 4)
    method(50, coins)

    7 事例七

    钢条切割,已经各长度的钢条和对应的收益,问长度为n的钢条怎么切割收益最大。

    要求长度为n的钢条切割最大收益,则在n-1最大收益+长度1的收益,n-2最大收益+长度2最大收益……中取最大者。那么依次求长度1~n的钢条最大收益即可。

    # 钢条长度与对应的收益
    length = (1, 2, 3, 4,5, 6, 7, 8, 9, 10)
    profit = (1, 5, 8, 9,10, 17, 17, 20, 24, 30)
     
     
    # 参数:profit: 收益列表, n: 钢条总长度
    def bottom_up_cut_rod(profit, n):
        r = [0] # 收益列表
        s = [0]*(n+1) # 切割方案列表
     
        for j in range(1, n+1):
            q = float('-inf')
            #每次循环求出长度为j的钢条切割最大收益r[j],s[j]则保存切割方案中最长的那一段长度
            for i in range(1, j+1):
                if max(q, profit[length.index(i)]+r[j-i]) == profit[length.index(i)]+r[j-i]:#元组index从1开始
                    s[j] = i#如果切割方案为1和2,那么2会覆盖1,即保存最长的一段
                q = max(q, profit[length.index(i)]+r[j-i])
     
            r.append(q)
            #r[n]保存长度为n钢条最大切割收益
        return r[n], s[n]
     
    # 切割方案
    def rod_cut_method(profit, n):
        how = []
        while n != 0:
            t,s = bottom_up_cut_rod(profit, n)
            how.append(s)
            n -= s
     
        return how
    #输出长度1~10钢条最大收益和最佳切割方案
    for i in range(1, 11):
        t1 = time.time()
        money,s = bottom_up_cut_rod(profit, i)
        how =  rod_cut_method(profit, i)
        t2 = time.time()
        print('profit of %d is %d. Cost time is %ss.'%(i, money, t2-t1))
        print('Cut rod method:%s\n'%how)

    8 事例八

    水杯摔碎问题,有n个水杯和k层楼,求最少测试几次可以确定水杯刚好在哪一层楼摔碎。

    解答过程:假设从x层楼开始扔为f(n,x),如果水杯碎了水杯数量-1需要探测的楼层为x-1层,则为f(n-1,x-1),如果没碎水杯还是n个需要探测k-x层,则为f(n,k-x)

    import numpy as np
     
    #n个水杯k层楼,最少需要几次测试确定水杯在几层楼刚好摔破
    def solvepuzzle(n, k):
        numdrops = np.array([[0]*(k+1)]*(n+1))
     
        for i in range(k+1):
            numdrops[1, i] = i#只有一个水杯,最坏情况是跟楼层数一样
     
        for i in range(2, n+1):#2到n个水杯
            for j in range(1, k+1):#楼层1到k
                minimum = float('inf')
                #每次循环得出一种(i,j)下的最少次数
                for x in range(1, j+1):
                    minimum = min(minimum, (1+max(numdrops[i, j-x], numdrops[i-1, x-1])))
                numdrops[i, j] = minimum
        print(numdrops)
        return numdrops[n,k]
     
    t = solvepuzzle(3, 10)
    print(t)

    9 事例九

    给定n个水杯和d次尝试机会,求最多能探测多少楼层。

    解答过程:f(d,n)=f(d-1,n)+f(d-1,n-1),令g(d,n)=f(d,n+1)-f(d,n)=g(d-1,n)+g(d-1,n-1),这跟二项式C(n,k)=C(n-1,k)+C(n-1,k-1)相似,故g(d,n)=C(d,n)-->f(d,n)=求和(C(d,i)) i从1到n-1,i>=d时C(d,i)=0

    
    #n个水杯d次尝试机会,最多探测多少层楼?
    #f(d,n)=求和i=1~n-1{C(d,i)} 对所有d>=1 and i<d
    def assist(d,i):#C(d,i)
    	sum=1
    	sum2=1
    	for k in range(d-i+1,d+1):
    		sum*=k
    	for j in range(1,i+1):
    		sum2*=j
     
    	sum=sum/sum2
    	return sum
     
    def f(d,n):
    	if d<1 or n<1:
    		return 0
    	elif d==1:
    		return 1
    	sum=0
    	for i in range(1,n+1):
    		if i<d:
    			sum+=assist(d,i)
    	return int(sum)
    print(f(3,3))
    #这里可以逆向求解n个水杯k层楼至少需要多少次测试
    def reverseFun(n,k):
    	d=1
    	while f(d,n)<k:
    		d+=1
    	print(d)
    	return d
    reverseFun(3,10)

     

    展开全文
  • 文章目录1.序2.动态规划的基本概念[^1]3.动态规划算法的基本思想[^2]4....这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...

    1.序

    近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。

    2.动态规划的基本概念[^1]

    在学习动态规划之前,先思考这样一个问题:什么是动态规划?为什么叫动态规划?
    当读者在试图探索这个问题的时候,不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的,应用于工程领域。
    动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

    所谓多阶段决策过程是指这样一类决策过程:它可以把一一个复杂问题按时间(或空间)分成若干个阶段,每个阶段都需要作出决策,
    以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何,不但与该阶段的经济效果有关,
    还影响以后各阶段的经济效果,可见这类多阶段决策问题是一个动态的问题,因此,处理的方法称为动态规划方法。然而,动态
    规划也可以处理一些本来与时间没有关系的静态模型,这只要在静态模型中人为地引入“时间”因素,分成时段,就可以把它看作
    是多阶段的动态模型,用动态规划方法去处理。
    

    简言之,多阶段决策过程是指这样的一类特殊的活动过程:问题可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。
    下面举例说明什么是多阶段决策问题。
    例1(最短路线问题)在线路网络图1中,从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离,为使总运费最少,必须找出一条由A至E总里程最短的路线。
    在这里插入图片描述

    图1

    为了找到由A至E的最短线路,可以将该问题分成A—B—C—D—E 4个阶段,在每个阶段都需要作出决策,即在A点需决策下一步到B1还是到B2或B3;同样,若到达第二阶段某个状态,比如B1 ,需决定走向C1还是C2 ;依次类推,可以看出:各个阶段的决策不同,由A至E的路线就不同,当从某个阶段的某个状态出发作出一个决策,则这个决策不仅影响到下一个阶段的距离,而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策,使这些决策序列所决定的一条路线对应的总路程最短。

    3.动态规划算法的基本思想[^2]

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。
    在这里插入图片描述

    图2

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
    在这里插入图片描述

    图3

    4.动态规划的求解步骤[^2]

    a. 找出最优解的性质,并刻划其结构特征。
    b. 递归地定义最优值。
    c. 以自底向上的方式计算出最优值。
    d. 根据计算最优值时得到的信息,构造最优解

    5.动态规划算法的基本要素[^2]

    5.1 最优子结构

    • 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
    • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。
    • 利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

    注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)

    5.2 重叠子问题

    • 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
    • 动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。
    • 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
      在这里插入图片描述
      图4

    6.一些经典的动态规划问题

    这部分待补充~
    笔者要充电了~

    参考文献
    [1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
    [2]引用自老师的课件

    展开全文
  • 动态规划算法介绍

    千次阅读 2019-02-17 19:34:49
    动态规划算法及其应用 动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划算法的思想和分治算法类似,基本思想也是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原...
  • 动态规划算法 算法介绍 动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法 动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,078
精华内容 11,631
关键字:

动态规划算法