五大常用算法之二： 动态规划算法1

漫画:什么是动态规划？

一、基本概念

动态规划过程是：每个决策都依赖于当前的状态，然后导致状态的转移。决策序列是在不断变化的状态下产生的，因此多阶段优化决策解决问题的过程称为动态规划。

二、基本思想和策略

与分治法相似，基本思想也将待解决的问题分解为几个子问题（阶段），并按顺序解决子阶段。前一个子问题的解决为后一个子问题的解决提供了有用的信息。在解决任何子问题时，列出各种可能的局部解决方案，通过决策保留可能达到最佳的局部解决方案，并丢弃其他局部解决方案。依次解决各子问题，最后一个子问题是解决初始问题。

由于动态规划解决的大多数问题都具有重叠子问题的特点，为了减少重复计算，每个子问题只解决一次，并在二维数组中保存不同阶段的不同状态。

适用于动态规划法解决的问题，分解后得到的子问题往往不是独立的（即下一个子阶段的解决是基于上一个子阶段的解决）。

三、适用情况

能够通过动态规划解决的问题一般有三个性质：

(1) 最优化原理:如果问题的最优解包含的子问题的解也是最优的，那么问题就有最优的子结构，即满足最优化原理。

(2) 无后效性：即一旦确定了一个阶段的状态，它就不会受到未来决策的影响。也就是说，一个状态后的过程不会影响以前的状态，而只与当前的状态有关。

（3）存在重叠子问题：即子问题不是独立的，子问题可以在下一阶段的决策中多次使用。（这种性质不是适用于动态规划的必要条件，但如果没有这种性质，动态规划算法与其他算法相比就没有优势）

四、求解的基本步骤

动态规划处理的问题是一个多阶段的决策问题，通常从初始状态开始，通过选择中间阶段的决策来结束。这些决策形成了一个决策序列，并确定了一条完成整个过程的活动路线（通常是最佳的活动路线）。如图所示。动态规划的设计有一定的模式，通常需要经历以下步骤。

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

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

分阶段：根据问题的时间或空间特征，将问题分为几个阶段。分阶段时，注意分阶段必须有序或可排序，否则问题无法解决。

确定状态和状态变量：用不同的状态表示问题发展到每个阶段的各种客观情况。当然，状态的选择应满足无后效性。

确定决策并编写状态转移方程：由于决策与状态转移有自然的联系，因此状态转移是根据上一阶段的状态和决策导出本阶段的状态。因此，如果确定了决策，也可以编写状态转移方程。但事实上，决策方法和状态转移方程往往是根据相邻两个阶段状态之间的关系来确定的。

寻找边界条件：给出的状态转移方程为递推式，需要递推终止条件或边界条件。

当确定阶段、状态和状态转移决策时，可以编写状态转移方程（包括边界条件）。

在实际应用中，可根据以下简化步骤进行设计：

(1)分析最优解的性质，描绘其结构特征。

(2)递归定义最优解。

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

(4)根据计算最优值时获得的信息，对结构问题进行最优解决。

五、算法实现的说明

动态规划的主要难点在于理论设计，即以上四个步骤的确定。一旦设计完成，实现部分将非常简单。

最重要的是确定动态规划的三要素：

(1)问题阶段

每个阶段的状态

(3)从前一阶段到后一阶段的递推关系。

递推关系必须从次小问题转变为大问题。从这个角度来看，动态规划往往可以通过递归程序来实现，但因为可以充分利用前面保存的子问题的解决方案来减少重复计算，因此，对于大规模问题来说，递归具有无与伦比的优势，这也是动态规划算法的核心。

整个解决过程可以用最优决策表来描述。最优决策表是二维表，其中银行表示决策阶段，列表示问题状态。表格中需要填写的数据一般对应于某一阶段某一状态下问题的最优值(如最短路径、最长公共子序列、最大值等。)，填写表格的过程是根据递推关系依次填写表格。最后，根据整个表格的数据，通过简单的选择或操作获得问题的最佳解决方案。

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

六、动态规划算法基本框架

代码

1    for(j=1; j<=m; j=j+1) // 第一个阶段 2   xn[j] = 初始值; 3  4  for(i=n-1; i>=1; i=i-1)// 其他n-1阶段 5   for(j=1; j>=f(i); j=j+1)//f(i)与i相关的表达式 6  xi[j]=j=max(或min){g(xi-1[j1:j2]), ..., g(xi-1[jk:jk+1])}; 8  9 t = g(x1[j1:j2]); // 解决整个问题的最佳解决方案10 11 print(x1[j1];12 13 for(i=2; i<=n-1; i=i+1）15 { 17  t = t-xi-1[ji];18 19  for(j=1; j>=f(i); j=j+1)21  if(t=xi[ji])23  break;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行的三角形，我们可以写以下递归式：

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)

根据上述简单的递归式，我们可以很容易地写出完整的递归代码：

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为例。当我们计算从第二行数字3开始的MaxSum时，我们会计算从1开始的MaxSum。当我们计算从第二行数字8开始的MaxSum时，我们会再次计算从1开始的MaxSum，即重复计算。这浪费了很多时间。也就是说，如果采用递规的方法，每条路径都会有大量的重复计算。时间复杂度为 2n次方，对 n = 100 好吧，一定要加班。

接下来，我们必须考虑如何改进，我们自然会认为，如果我们计算每个MaxSum，(r,j)保存下来，下次直接使用时，可以避免重复计算。然后计算可以用n方的时间复杂度来完成。因为三角形的总数是 n(n+1)/2

根据这一思路，我们可以改进上述代码，使其成为记忆递归型的动态规划程序：

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。以此类推。。下图我们可以得到：

然后按照同样的原则分析倒数第三行和倒数第四行，最后分析第一行，我们可以依次得到以下结果:

相信大家都不难理解以上的推导过程。理解后，我们可以编写以下递推动态规划程序：

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. for( int i = 1;i <= n; ++ i )       17.         maxSum[n][i] = D[n][i];     18. for( int i = n-1; i>= 1;  --i )       19. for( int 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值即可。

空间优化后的具体递推过程如下：

下一步可以根据上图的过程逐步推导。进一步考虑，我们甚至可以直接用D的第n行代替maxsum，而不是maxsum数组。但这里需要强调的是，虽然节省了空间，但时间复杂性保持不变。

按照上述方法，我们可以写下以下代码：

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指向第n行      18. for( int i = n-1; i>= 1;  --i )       19. for( int 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) 没有后效性。一旦确定了当前的几个状态值，后续过程的演变只与这些状态值有关，与之前采用的手段或路径演变为当前的状态无关。

数据结构与算法