总结一下《算法导论》中对动态规划的介绍。
动态规划通常用来求最优解，应用于子问题相互重合的情况，即许多子问题中有许多公共的、相同的更小的子问题，如果用分治法可能会重复多次的计算它们，为了避免重复计算，我们使用动态规划。
一般来说分为四个步骤：
-
刻画出一个最优解的结构特征
-
递归的定义最优解的值
-
计算最优解的值，通常以自下而上的方式（bottom-up）
-
通过计算最优解得到的信息重构出最优解
步骤1~3是算法的基础，如果我们只需要得到最优解的值，则可以忽略步骤4。而如果需要得到最优解本身，就需要额外维护一些信息，以便在得到最优解值后重构出最优解。下面看一些例子。
钢条切割
题目描述：
给定一个长度为n的钢条和一个价格表（数组）p[i](i=1, 2, …, n)，求钢条的最佳切割方案，使得收益r[n]最大（注意最优解存在不切割的情况）。
显而易见，对于一个长为n的钢条，共有n-1处位置选择切或不切，因此共有2^(n-1)种不同的切割方案。而对于最佳收益r[n]，我们可以用更短钢条的最优解来描述：
r[n] = max(p[n], r[1] + r[n-1], r[2] + r[n-2], ..., r[n-1] + r[1])
由此看来，长度为n的钢条的最优解为将其分为两段的所有可能中组合收益的最大者，也就是由子问题最优解组成，而这些子问题可以独立求解。我们从另一个角度来分割，即将钢条二分后对左边的一段不再进行切割，此时问题被分解为：将长度为n的钢条分解为左边开始一段，以及剩余部分继续分解的结果，这样上面的公式可以进一步简写为
r[n] = max(p[i] + r[n-i]), 1 <= i <= n
我们利用递归很容易可以实现：
int cut_rod(vector<int> p, int n){
if(n == 0)
return 0;
int q = INT_MIN;
for(int i = 1; i <= n; i++){
q = max(q, p[i] + cut_rod(p, n - i));
}
return q;
}
这个程序在实现上没有问题，但是效率奇差，递归式T(n) = 1 + sum(T(j))，j从0到n-1，T(0) = 1，很容易证明最终T(n) = 2^n，也就是说这种算法的时间复杂度是指数级的，这就是我们上面提到的问题所致，它重复计算了很多子问题。为了解决这个问题，我们对每个子问题只求解一次，并将结果保存，后面需要时直接调用，说简单点就是用付出额外的空间来节省计算时间，但其中的收益是巨大的。下面介绍两种等价的动态规划实现：
带备忘的自顶而下（top-down with memoization）
这种方法仍然用前面的递归思路，只是会在中途保存已经计算过的解，在计算前首先查看是否已经得到答案，如果是则直接调用，如果不是再计算。
下面是改写后的cut_rod函数：
vector<int> r(n + 1, INT_MIN);
int cut_rod_memo(vector<int> p, int n, vector<int> r){
if(r[n] >= 0)
return r[n];
int q;
if(n == 0)
q = 0;
else{
q = INT_MIN;
for(int i = 1; i <= n; i++)
q = max(q, p[i] + cut_rod_memo(p, n - i, r));
}
r[n] = q;
return q;
}
首先初始化一个数组r，大小为n+1初始值为负无穷，这样在比较中可以轻易分辨哪些最优解已经被保存，从而直接返回那些已经被保存了的值，而如果还没有计算，那么在计算完成后将r中相应的位置赋上值得到的结果，为之后的计算提供帮助。
自底而上法（bottom-up method）
这种方法需要恰当定义子问题的规模，并在计算时按规模排序，按由小到大的规模顺序求解，当求某个子问题时，它所需的那些更小的子问题已经求解完毕，因此免去了重复计算的麻烦，也就是说当我们计算最优解时，所有的子问题都已经提前求解完成。
int bottomUp_cut_rod(vector<int> p, int n){
vector<int> r(n + 1);
for(int j = 1; i <= n; j++){
int q = INT_MIN;
for(in i = 1; i <= j; i++){
q = max(q, p[i] + r[j - i]);
}
r[j] = q;
}
return r[n];
}
对于一个长为n的钢条，我们要得到长为n时的最佳切割方案带来的收益，也就是最优解值，需要的是前面规模为0到n-1长度钢条的全部最优解值，假设我们已经得到了它们，那么长为n的钢条的最大收益就是前面分析过的，取将其切割一次后的所有情况收益的最大值（切割一次指的是将钢条从某处切断后，左边子钢条的本身价值，加上右边子钢条的收益最大值）。要得到这个最大值，只需要比较将其二分的所有情况，即
max(p[i] + r[n - i])
这里i取1~n，不从零开始是因为p从1开始，如果从零开始就相当于左顶端不切，而且不切就相当于要知道右端长度为n的钢条的最大收益，而这正是我们需要得到的值。注意这和取到n不一样，因为长度为n的钢条本身的价值是已知的（p[n]），而它的最优解是未知的，取n的意义相当于我右顶端不切，可以得到多少收益，这个收益就是p[n]，因为我们已经将r[0]初始化为零，再和其他情况比较。
这个方法和上面那种本质上并没有区别，不同的只是比较最大值时这里用的是数组中储存的更短钢条的最优解，而上面用的是递归函数的结果。 自底而上的方法更为常见，也可能带来更高的效率，因为不需要借助递归。
这两种方法的时间复杂度都是O(n^2)。
重构解
一般题目只会让我们给出最优解值，而不需要提供具体的最优解，但如果题目要求，也需要知道重构方法。
要想重构出最优解，只需要在原来的代码中加入一个数组储存数据：
vector<int> s(n + 1);
int bottomUp_cut_rod(vector<int> p, int n){
vector<int> r(n + 1);
for(int j = 1; i <= n; j++){
int q = INT_MIN;
for(in i = 1; i <= j; i++){
if(q < p[i] + r[j - i]){
q = p[i] + r[j - i];
s[j] = i;
}
}
r[j] = q;
}
return r[n];
}
int main(){
// ... 处理输入
int ans = bottomUp_cut_rod(p, n);
while(n>0){
cout << s[n] << ' ';
n = n - s[n];
}
return 0;
}
总结
当思考一个动态规划问题时，我们应该弄清楚楚所涉及的子问题以及子问题之间的依赖关系。如果我们画出它的子问题图，即对于一个给定子问题x，在求解它之前求解邻接至它的子问题y，换句话说，对于任何子问题，直至它所依赖的所有子问题均已求解完成，才会求解它，这其实可以理解为一种深度优先搜索（depth-first search）。由于每个子问题只求解一次，因此算法的运行时间为每个子问题求解时间之和，通常一个子问题的求解时间与子问题图中对应顶点的度（也就是边的数目）成正比，而子问题的个数就等于问题图中顶点的个数，因此我们动态规划算法的运行时间与顶点和边的数量呈线性关系。