前言
和分治法一样，动态规划（dynamic programing）是通过组合子问题的解而解决整个问题的。注意这里的programing翻译成立规划而不是编程。维基百科上写道
This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger subproblems by using the solutions to small subproblems.
这说明动规的关键是table,是子问题。而且动规的子问题是相互关联的。而分治算法是将问题划分成相对独立的子问题，递归的解决所有子问题，
然后合并子问题成为最终的结果。在这个过程中，分治法会做很多不必要的工作，即重复地求解公共子问题。
动规对每个子问题之求解一遍，并且将其结果保存在表中，从而避免了子问题被重复计算。
适用范围
1.动态规划通常情况下应用于最优化问题，这类问题一般有很多个可行的解，每个解有一个值，而我们希望从中找到最优的答案。
2.该问题必须符合无后效性。即当前状态是历史的完全总结，过程的演变不再受此前各种状态及决策的影响。
简单动态规划问题
最大子数组和问题
题目
一个有N个整数元素的一位数组(A[0], A[1],...,A[n-1], A[n])，这个数组当然有很多子数组，那么数组之和的最大值是什么呢？
这是一道很简单的题目，但是要想写出时间复杂度为O(n)的最优解法还是需要仔细推敲下的。
例如有数组 int A[5] = {-1, 2, 3, -4, 2};
符合条件的子数组为 2,3 即答案为 5;
再明确一下题意
1.子数组必须是连续的。
2.不需要返回子数组的具体位置。
3.数组中包含：正整数，零，负整数。
例如
数组： {1, -2, 3, 5, -3, 2} 返回值为 8
数组： {0, -2, 3, 5, -1, 2} 返回值为 9
数组： {-9, -2, -3, -5, -6} 返回值为 -2 注意子数组不能为空
首先我们看看最直接的穷举法
int MaxSubString(int* A, int n)
{
int max = min; //初始值为负无穷大
int sum;
for(int i = 0; i < n; i++)
{
sum = 0;
for(int j = i; j < n; j++)
{
sum += A[j];
if(sum > max)
max = sum;
}
}
return max;
}
这种方法最直接，当也是最耗时的，他的时间复杂度为O(n^2);
问题分析
可以优化吗？答案是肯定的，可以考虑数组的第一个元素，以及最大的一段数组(A[i], ..., A[j]),和A[0]的关系，有一下几种情况：
1. 当0 = i = j 时，元素A[0]本身构成和最大的一段;
2. 当0 = i < j 时，和最大的一段以A[0]开始;
3. 当0 < i 时， 元素A[0]和最大的一段没有关系。
从上面3中情况可以看出。可以将一个大问题(N个元素数组)转化为一个较小的问题(N-1个元素的数组)。假设已经知道(A[1], ...,A[n-1])中和最大的一段数组之和为All[1],并且已经知道
(A[1],...,A[n-1])中包含A[1]的和最大的一段数组为Start[1]。那么不难看出 (A[0], ..., A[n])中问题的解All[0] = max{ A[0], A[0] + start[1], All[1] }。通过这样的分析，可以看出这个问题
无有效性，可以用动态规划来解决。
解决方案
int MaxSubString(int* A, int n)
{
int Start = A[n - 1];
int All = A[n - 1];
for(int i = n - 2; i >= 0; i--) //从后向前遍历，反之亦可。
{
Start = max( A[i], A[i] + Start);
All = max(Start, All);
}
return All[0]; //All[0] 中存放结果
}
我们通过动规算法解决该问题不仅效率很高(时间复杂度为O(n)),而且极其简便。
01背包问题
题目
这题非常有名，只要是计算机专业的应该都有听说过。有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
我们把题目具体下， 有5个商品，背包的体积为10，他们的体积为 c[5] = {3,5,2,7,4}; 价值为 v[5] = {2,4,1,6,5};
问题分析
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。可以将背包问题的求解看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些不放入背包。
如果一个问题的最优解包含了物品n，即Xn = 1，那么其余X1, X2, .....,Xn-1 一定构成子问题1,2,.....,n-1在容量C - cn时的最优解。如果这个最优解不包含物品n,即Xn = 0;
那么其余 X1, X2.....Xn-1一定构成了子问题 1,2,....n-1在容量C时的最优解。 //请各位仔细品味这几句话
根据以上分析最优解的结构递归定义问题的最优解 f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + v[i]}
解决方案
#include<iostream>
#define max(a,b) ((a) > (b) ? a : b)
int c[5] = {3,5,2,7,4};
int v[5] = {2,4,1,6,5};
int f[6][10] = {0};
//f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + w[i]}
int main()
{
for(int i = 1; i < 6; i++)
for(int j = 1; j < 10 ;j++)
{
if(c[i] > j)//如果背包的容量，放不下c[i]，则不选c[i]
f[i][j] = f[i-1][j];
else
{
f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + v[i]);//转移方程式
}
}
std::cout<<f[5][9];
return 0;
}
01背包问题是最基本的动态规划问题，也是最经典，最易懂的。所以请读者仔细推敲这段代码。它包含了背包问题中设计状态、方程的最基本思想。
矩阵连乘问题
题目
给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的，i = 1,2, ...n-1。考虑这n个矩阵的乘积。由于竞争乘法满足结合律，故计算矩阵的连乘有许多不同的计算次序。
这种计算次序可以用加括号的方式确定。若一个矩阵连乘的计算次序完全确定，这是就说该连乘已完全加括号。
例如，矩阵连乘A1 *A2 *A3 *A4 可以有5种完全加括号的方式：（A1 *（A2 *（A3 *A4 ）））， （A1 *（（A2 *A3） *A4）），（（A1 *A2 ）*（A3 *A4）），
（（（A1 *A2 ）*A3 ）*A4）。每种加括号的方式确定了一个计算的次序。不同的计算次序与矩阵连乘的计算量有密切的关系。关于矩阵如何相乘这里我就不赘述了请看about matrix 。
考虑3个矩阵{A1,A2,A3}连乘的例子，假设这3个矩阵的维数分别为 10×100， 100×5， 5×50。若按照((A1*A2)*A3)计算，则计算次数为10×100×5 + 10×5×50 = 7500
若按(A1*(A2*A3))计算，则计算次数为 100×5×50 + 10×100×50 = 75000。第1种方法的计算次数是后者的10倍！由此可以看出，不同的加括号方式确定不同的计算次序对
矩阵乘法的运算量影响是巨大的。
矩阵连乘为题定义如下：给定n个矩阵{A1,A2,...,An}，矩阵A1的维数为pi-1×pi, i = 1,2, ..., n，如何给矩阵连乘A1*A2*....*An完全加上括号使用矩阵乘法中计算次数最少。
问题分析
若用穷举法，能够证明需要指数时间来求解。但是时间代价高昂。现在考虑用动态规划来求解连乘问题。
为方便起见用Ai...j表示矩阵乘法Ai*Ai+1*....Aj的结果。其中i<j。那么Ai*Ai+1*.....Aj一定在Ak与Ak+1之间被分裂。i <= k < j。问题Ai*Ai+1 ... Aj完全加括号的开销等于计算矩阵
Ai...k 与计算 Ak+1...j的开销，再加上他们的结果相乘的开销。问题的最优子结构可以描述如下：假定问题Ai*Ai+1*...Aj被完全加括号的最优方式是在Ak与Ak+1之间被分裂，那么分裂
之后，最优解Ai*Ai+1*....Aj中的子链Ai*Ai+1....Ak一定是问题Ai*Ai+1*...*Ak的最优加括号方式。同样，最优解Ak+1*Ak+2*...Aj的子链一定是问题Ak+1*Ak+2*...Aj最优加括号方式。
根据上面分析，设m[i,j]表示计算Ai...j所需的最小计算次数 m[i,j] = min{m[i,k]+m[k+1,j]+pi-1pKpj }
解决方案
#include<iostream>
void main()
{
int m[8][8], min;
int r[8] = {10, 20, 50, 1, 100, 4, 20, 2}; /* 矩阵维数 */
/* 初始化 */
memset(m,0,sizeof(m));
/* 每此增量加一 */
for (int l = 1; l < 7; l++)
{
/* 对于差值为 l 的两个元素 */
for (int i = 1; i <= 7 - l; i++)
{
j = i + l;
/* 求其最小组合方式 */
min = m[i][i] + m[i+1][j] + r[i-1] * r[i] * r[j];
middle[i][j] = i;
for (int k = i + 1; k < j; k++)
{
if (min > m[i][k] + m[k+1][j] + r[i-1] * r[k] * r[j])
{
min = m[i][k] + m[k+1][j] + r[i-1] *r[k]* r[j];
middle[i][j] = k;
}
}
m[i][j] = min;
}
}
std::cout<<m[1][N];
}
由以上代码可以很容易看出算法的时间复杂度为O(n^3)。即便如此也比穷举法的指数级时间复杂度快。
尾声
动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题，去设计状态转移方程式。
动态规划还有很多变形，如状态压缩，树形等等。这些题目虽然很难，但是工作学习之余，一边听歌，一边推敲。也是人生一大快事
作者: Bourbon 发表于 2011-08-23 22:15 原文链接
最新新闻：
· Y Combinator 举办 Demo Day，63 家创业公司亮相(2011-08-24 12:16)
· iPhone 5将支持CDMA/GSM双模(2011-08-24 12:09)
· Google+最新更新将出现在Gmail联系人栏目中(2011-08-24 12:06)
· 软件正在通吃所有工作(2011-08-24 12:05)
· 苹果两大成功动力：乔布斯文化与软硬件结合(2011-08-24 11:59)
编辑推荐：Hack, Everything!