一、动态规划的概念 #
动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。
动态规划方法通常用来求解最优化问题(optimization problem)。这类问题通常有很多可行的解，每一个解都有一个值，我们希望寻找具有最优值的解。我们称这样一个解为问题的一个最优解，而不是唯一的最优解，因为可能有多个解都达到最优值。
通常我们通过如下四个步骤设计一个动态规划算法：
- 刻画一个最优解的结构特征
- 递归地定义最优解的值
- 计算最优解的值，通常采用自底而上的方法
- 利用计算出的信息构造一个最优解
步骤1～3是动态规划算法求解问题的基础，如果我们仅仅需要一个最优解的值，而不是解本身就可以忽略步骤4，有时就需要在执行步骤3的过程中去维护一些额外的信息，以便用来构造一个最优解。
举例说明 #
给定一个r行的数字三角形（r <= 1000），需要找到一条从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到当前点左下方的点或右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面这个例子中，最优路径是7->3->8->7->5。
最简单粗暴的思路是尝试所有的路径。因为路径条数是 O(2^r)级别的，这样的做法无法接受。
注意到这样一个事实，一条最优的路径，它的每一步决策都是最优的。
以例题里提到的最优路径为例，只考虑前四步7->3->8->7 ，不存在一条从最顶端到4行第2个数的权值更大的路径。
而对于每一个点，它的下一步决策只有两种：往左下角或者往右下角（如果存在）。因此只需要记录当前点的最大权值，用这个最大权值执行下一步决策，来更新后续点的最大权值。
这样做还有一个好处：我们成功缩小了问题的规模，将一个问题分成了多个规模更小的问题。要想得到从顶端到第r行的最优方案，只需要知道从顶端到第r-1行的最优方案的信息就可以了。
这时候还存在一个问题：子问题间重叠的部分会有很多，同一个子问题可能会被重复访问多次，效率还是不高。解决这个问题的方法是把每个子问题的解存储下来，通过记忆化的方式限制访问顺序，确保每个子问题只被访问一次。
二、什么时候可以使用动态规划 #
从一个例子说起 #
先来看看生活中经常遇到的事吧——假设你是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。
这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。
但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：
15=1×11+4×1（贪心策略使用了5张钞票） 15=3×5 （正确的策略，只用3张钞票）
贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。 在这里我们发现，贪心是一种只考虑眼前情况的策略
重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。 那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？
明显cost=f(4)+1=4+1=5，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。 依次类推，马上可以知道：如果我们用5来凑出15，cost就是f(10) + 1 = 2 + 1 = 3。
那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个！
取11 -cost = f(4)+1 = 4+1=5 取10 -cost = f(5)+1 = 2+1=3 取1 -cost = f(14)+1 = 4+1=5
显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策！
这给了我们一个至关重要的启示—— f(n)只与 f(n−1),f(n−5),f(n−11) 相关；更确切地说：
f(n)=min{f(n−1),f(n−5),f(n−11)}+1
这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。代码如下：
#include<iostream>
using namespace std;
int main(){
int f[105], i, n, cost;
cin >> n;
f[0] = 0;
for(int i = 1; i <= n; i++){
cost = INT_MAX;
if(i - 1 >= 0) cost = min(cost, f[i - 1] + 1);
if(i - 5 >= 0) cost = min(cost, f[i - 5] + 1);
if(i - 11 >= 0) cost = min(cost, f[i - 11] + 1);
f[i] = cost;
cout << f[i] << endl;
}
}
我们以 O(n)的复杂度解决了这个问题。现在回过头来，我们看看它的原理：
– f(n)只与f(n−1),f(n−5),f(n−11)的值相关。
– 我们只关心 f(w)的值，不关心是怎么凑出w的。
这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”
这就是DP（动态规划，dynamic programming）.
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。
最优化原理 #
回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).
f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。
大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。
引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？
能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
无后效性原则 #
一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。
要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。
“未来与过去无关”，这就是无后效性。
严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。
三、动态规划用例 —— 最短路问题 #
最短路径问题 #
多段图的最短路径问题为从源点到终点的最小代价路径。如下图所示，每条线上的数字为经过这条路径需要付出的代价，问题为选择怎样的路径才能使所付出的代价最小。
问题分析 #
根据多段图的性质，我们可以将这种特殊的图结构划分为多个子集，例如如图所示的多段图就可以分成 5 个子集，在图中以 5 种不同颜色来表示。可以明显地看到想要到达某一个子集的顶点，就必须从上一个相邻顶点集的顶点出发，不相邻的子集之间不存在可达的边。针对这个特性可以推导出解决问题的方法，例如我想要到达顶点 10，那就必须要先到达顶点 8 或者顶点 9。换句话说，到达顶点 10 的最短距离就是在到达顶点8的最短距离 d(1,8) 加上边 (8,10) 的权重，和到达顶点 9 的最短距离 d(1,9) 加上边 (9,10) 的权重中取最小值。因为不相邻的顶点集之间不存在边，所以到达顶点 10 的方式有且仅有上述 2 种。设 C 为某条边的权重，d(m,n) 为从点 m 到点 n 的最短距离，则使用数学语言的描述如下：
再看一个例子，假设要分析到达顶点 8 的最短距离，则只有 3 种情况。即到达顶点 5 的最短距离 d(1,5) 加上边 (5,8) 的权重，和到达顶点 6 的最短距离 d(1,6) 加上边 (6,8) 的权重，和到达顶点 7 的最短距离 d(1,7) 加上边 (7,8) 的权重三者之间取最小值。使用数学语言的描述如下：
根据上面 2 个例子的论述，我们可以把情况从特殊推广到一般情况，设 Cuv 为多段图有向边 <u,v>的权值，源点 s 到终点 v 的最短路径长为 d(s,v)，终点为 t，则可以得到该问题的状态转移方程为：
#
参考程序 #
首先定义图结构的结构体，使用邻接矩阵来存储：
typedef struct //图的定义
{
int edges[MAXV][MAXV]; //邻接矩阵
int n; //顶点数
} MGraph;
定义求解问题需要的辅助结构：
MGraph topography; //保存城市关系的邻接矩阵
int path[MAXV] = {}; //保存到该顶点的最短路径对应的前驱
int min_cost[MAXV] = {}; //保存到每个顶点的最短路径长
要根据测试样例数据建立多段图的邻接矩阵：
MGraph CreateMGraph(int num) //建图
{
MGraph topography;
int n;
int point1, point2;
int value;
//初始化边为不存在
for(int i = 1; i <= num; i++)
{
for(int j = 1; j <= num; j++)
{
topography.edges[i][j] = 0;
}
}
cout << "请输入边数：";
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> point1 >> point2 >> value;
topography.edges[point1][point2] = value;
}
cout << "\n建立的邻接矩阵为：" << endl;
for(int i = 1; i <= num; i++)
{
for(int j = 1; j <= num; j++)
{
printf("%2d ",topography.edges[i][j]);
}
cout >> endl;
}
cout >> endl;
topography.n = num;
return topography;
}
根据状态转移方程求解问题，最后输出最短路径及其开销：
int main()
{
int cities_num = 0; //城市数量
int a_cost; //当前路径的开销
int pre;
cout << "城市数量为：";
cin >> cities_num;
//建图
topography = CreateMGraph(cities_num);
//初始化路径开销
min_cost[1] = 0;
for(int i = 2; i <= topography.n; i++)
{
min_cost[i] = 99999;
}
//依次计算到达所有点的最短路径
for(int i = 2; i <= cities_num; i++)
{
//遍历之前的所有点，计算到达该点的最短路径
for(int j = 1; j < i; j++)
{
if(topography.edges[j][i] != 0) //若路径存在
{
a_cost = min_cost[j] + topography.edges[j][i];
if(a_cost < min_cost[i]) //更新最短路径长
{
min_cost[i] = a_cost;
path[i] = j; //记录前驱顶点
}
}
}
}
//输出到所有顶点的最短路径
for(int i = 1; i <= cities_num; i++)
{
cout << "到顶点" << i << "的最小开销为：" << min_cost[i] << "，路径：" << i;
pre = i;
while(path[pre])
{
cout << "<-" << path[pre];
pre = path[pre];
}
cout << endl;
}
return 0;
}
