经典算法宝典——动态规划思维(六)(1)
动态规划（Dynamic Programming）主要针对最优化问题。所谓“规划”在现代汉语词典中是这样解释的：“规划是比较全面的长远的发展计划。”在动态规划算法策略中，这个解释体现在它的决策不是线性的而是全面考虑各种不同的情况分别进行决策，最后通过多阶段决策逐步找出问题的最终解。当各个阶段采取决策后，会不断决策出新的数据，直到找到最优解。每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。所以，这种多阶段最优化决策解决问题的过程称为动态规划。
一、动态规划算法设计框架
1、适用动态规划策略解决的问题的特征
适用动态规划算法解决的问题及其决策策略应该具有3个性质：最优化原理、无后向性、子问题重叠性质。
(1)最优化原理：（或称为最佳原则、最优子结构）如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2)无后向性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说某状态以后的过程不会影响以前的状态，只与当前状态有关，这种特性也被称为无后效性。
(3)子问题重叠：也就是说子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。对有分解过程的问题还表现在自顶向下分解问题时，每次产生的子问题并不总是新问题，有些子问题会反复出现多次。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。
2、动态规划的基本思想
动态规划的基本思想是，把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
说明：
由于动态规划解决的问题多数有重叠子问题这个特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
3、设计动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行。
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
(2)选择状态：将问题发展到各个阶段时所出现的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：之所以把这两步放在一起，是因为状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。这就像是“递推”，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
一般来说，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件），这些都是动态规划的基本工作。阶段的划分是关键，必须依据题意分析，寻求合理的划分阶段（或子问题）的方法。而每个阶段（或子问题）得到的是一个比原问题简单的优化问题。而且每个子问题的求解中，均利用它的一个前一个阶段（或子问题）的最优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。
实际应用当中可以按以下几个简化的步骤进行设计：
(1)分析最优解的性质，并刻画其结构特征。
(2)递推定义最优值。
(3)以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
(4)根据计算最优值时得到的信息，构造问题的最优解。
4、动态规划算法基本框架
动态规划策略在不同问题的应用中表现形式多样，不易给出清晰、易懂的基本框架。
for(j = 1; j <= m; j++) // 第一个阶段
x(n)[j] = 初始值;
for(i = n-1; i >= 1; i--) // 其他n-1个阶段
for(j = 1; j >= f(i); j++) // f(i)与i有关的表达式
x(i)[j] = max(或min){g(x(i-1)[j(1): j(2)]), ..., g(x(i-1)[j(k): j[k+1])};
t = g(x(1)[j(1): j(2)]); // 由最优解求解最优解的方案
print(x(1)[j(1)]);
for(i = 2; i <= n-1; i++)
{
t = t - x(i-1)[j(i)];
for(j = 1; j >= f(i); j++)
if(t = x(i)[j(i)])
break;
}
解析：
算法框架中f, g是某种函数，表示与当前表达式和函数中的参数有关；算法框架中i表示动态规划中的不同阶段，j表示每个阶段下考虑的多种情况；带下标的符号，如j(i)表示与阶段i有关的特定的情况j。算法框架中的x(i)[j] = max(或min){g(x(i-1)[j(1): j(2)]), ..., g(x(i-1)[j(k): j[k+1])};表达式，表示x(i)[j]与前一阶段的x(i-1)[j(1)] - x(i-1)[j(2)], ..., x(i-1)[j(k) - x(i-1)[j(k+1)]有关，取它们某种函数值有最大值（或最小值）。在实际的算法中，这一步可能也是一个循环结构。
二、认识动态规划
1、数塔问题
给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向左走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。
输入样例：
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
输出样例：
max = 59
9->12->10->18->10
阶段划分：
从数塔问题的特点来看，不难发现解决问题的阶段划分，应该是自下而上逐层决策。不同于贪心策略的是做出的不是唯一的决策，第一步对于第五层的8个数据，做如下4次决策：
- 对经过第四层2的路径，在第五层的19，7中选择19；
- 对经过第四层18的路径，在第五层的7，10中选择10；
- 对经过第四层9的路径，在第五层的10，4中也选择10；
- 对经过第四层5的路径，在第五层的4，16中选择16。
这是一次决策过程，也是一次递推过程和降阶过程。因为以上的决策结果将5阶数塔问题变为4阶子问题，递推出第四层与第五层的和为：
21(2 + 19), 28(18 + 10), 19(9 + 10), 21(5 + 16)
用同样的方法还可以将4阶数塔问题，变为3阶数塔问题，...，最后得到的1阶数塔问题，就是整个问题的最优解。
存储求解：
1)原始信息存储
原始信息有层数和数塔中的数据，层数用一个整型变量n存储，数塔中的数据用二维数组data，存储成如下的下三角阵：
9
12 15
10 6 8
2 18 9 5
2)动态规划过程存储
由于早期阶段动态规划决策的结果是一组数据，且这次的决策结果是下次决策的唯一依据（无后效性），所以必须再存储每一次决策的结果，若仅仅是求最优解，用一个一维数组存储最新的决策结果即可；但若要同时找出最优解的构成或路径，则必须用二维数组d存储各阶段的决策结果。根据上面的算法设计，二维数组d的存储内容如下：
d[n][j] = data[n][j], j = 1, 2, ..., n;
当i = n-1, n-2, ..., 1, j = 1, 2, ..., i时：
d[i][j] = max(d[i+1][j], d[i+1][j+1]) + data[i][j]
最后d[1][1]存储的就是问题的结果。
数塔及动态规划过程数据，如下所示：
数组data 数组d
9 59
12 15 50 49
10 6 8 38 34 29
2 18 9 5 21 28 19 21
3)最优解路径求解及存储
通过数组data和数组d可以找到最优解的路径，但需要自顶向下比较数组data和数组d中的数据。
输出data[1][1]“9”。
b = d[1][1] - data[1][1] = 59 - 9 = 50，b与d[2][1]，d[2][2]比较，b与d[2][1]相等，输出data[2][1]“12”。
b = d[2][1] - data[2][1] = 50 - 12 = 38，b与d[3][1]，d[3][2]比较，b与d[3][1]相等，输出data[3][1]“10”。
b = d[3][1] - data[3][1] = 38 - 10，b与d[4][1]，d[4][2]比较，b与d[4][2]相等，输出data[4][2]“18”。
b = d[4][2] - data[4][2] = 28 - 18，b与d[5][2]，d[5][3]比较，b与d[5][3]相等，输出data[5][3]“10”。
说明：
据此，可以写出根据数组data和数组d求解最优解路径的算法。
算法实现：
为了提高算法的时间效率，还可以在动态规划的过程中，同时记录每一步决策选择数据的方向，这又需要一个二维数组。为了设计简洁的算法，最后用三维数组a[50][50][3]存储以上确定的3个数组的信息。a[50][50][1]代替数组data，a[50][50][2]代替数组d，a[50][50][3]记录解路径。
其中，a[50][50][3] = 0表示向下（在塔中是向左）“走”，如第三层2与下面的19求和；其中，a[50][50][3] = 1表示向右“走”，如第三层18与下面的10求和。
#include<iostream>
using namespace std;
int main()
{
int a[50][50][3], i, j, n;
cout << "please input the number of rows: ";
cin >> n;
for(i = 1; i <= n; i++)
for(j = 1; j <= i; j++)
{
cin >> a[i][j][1];
a[i][j][2] = a[i][j][1];
a[i][j][3] = 0;
}
for(i = n - 1; i >= 1; i--)
for(j = 1; j <= i; j++)
if(a[i+1][j][2] > a[i+1][j+1][2])
{
a[i][j][2] = a[i][j][2] + a[i+1][j][2];
a[i][j][3] = 0;
}
else
{
a[i][j][2] = a[i][j][2] + a[i+1][j+1][2];
a[i][j][3] = 1;
}
cout << "max = " << a[1][1][2] << endl;
j = 1;
for(i = 1; i <= n-1; i++)
{
cout << a[i][j][1] << "->";
j = j + a[i][j][3];
}
cout << a[n][j][1] << endl;
return 0;
}
结果输出：
总结：
贪婪算法的效率比较高，每次作出的是局部的、唯一的决策结果（所以贪婪策略适用的问题范围小）。而动态规划的每个阶段的决策，作出的是一组局部的决策结果。每个阶段都使问题规模变小，且更接近最优解，直到最后一步，问题的规模变为1，就找到了问题的最优解，算法结束。贪婪策略、递推算法都是在“线性”地解决问题，而动态规划则是全面分阶段地解决问题。可以通俗地说动态规划是“带决策的多阶段、多方位的递推算法”。