前言：动态规划的概念
动态规划（dynamic programming）是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分为一些独立的子问题，递归的求解各个问题，然后合并子问题的解而得到原问题的解。例如归并排序，快速排序都是采用分治算法思想。本书在第二章介绍归并排序时，详细介绍了分治算法的操作步骤，详细的内容请参考：http://www.cnblogs.com/Anker/archive/2013/01/22/2871042.html。而动态规划与此不同，适用于子问题不是独立的情况，也就是说各个子问题包含有公共的子问题。如在这种情况下，用分治算法则会重复做不必要的工作。采用动态规划算法对每个子问题只求解一次，将其结果存放到一张表中，以供后面的子问题参考，从而避免每次遇到各个子问题时重新计算答案。
动态规划与分治法之间的区别：
（1）分治法是指将问题分成一些独立的子问题，递归的求解各子问题
（2）动态规划适用于这些子问题不是独立的情况，也就是各子问题包含公共子问题
动态规划通常用于最优化问题（此类问题一般有很多可行解，我们希望从这些解中找出一个具有最优（最大或最小）值的解）。动态规划算法的设计分为以下四个步骤：
（1）描述最优解的结构
（2）递归定义最优解的值
（3）按自低向上的方式计算最优解的值
（4）由计算出的结果构造一个最优解
动态规划最重要的就是要找出最优解的子结构。
一 钢条切割
钢条切割问题描述：给定一段长度为n英寸的钢条和一个价格表Pi(i=1,2,3,...,n)，求切割钢铁方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格Pn足够大，最优解可能就是完全不需要切割。
假设一个最优解将钢条切割为k段（对某个1<=k<=n),那么最优切割方案
n=i1+i2+...+ik
将钢条切割的长度分别为i1,i2,...ik的小段，得到的最大收益
rn=pi1+pi2+...+pik
更一般地，对于rn(n>=1)，我们可以用更短的最优切割收益来描述它：
rn=max(pn,r1+r(n-1),r2+r(n-2),...,r(n-1)+r1)
第一个参数pn对应不切割，直接出售长度为n英寸的钢条的方案。其他n-1个参数对应另外n-1种方案：对每个i=1,2,...n-1，首先将钢条切割为长度为i和n-i的两端，接着求解这两段的最优切割收益ri和r(n-i)（每种方案的最优收益为两段的最优收益之和）。由于无法预知哪种方案会获得最大收益，我们必须考察所有可能的i，选取其中收益最大者。如果直接出售原钢条会获得最大收益，我们当然可以选择不做任何切割。
自顶向下递归实现
下面是一种直接的自顶向下的递归方法。
CUT-ROD(p,n) if n==0 return 0 q=-∞ for i=1 to n q=max(q,p[i]+CUT-ROD(p,n-i)) return q
C++实现代码：
#include<iostream> using namespace std; int cut_rod(int p[],int n) { if(n==1) return 0; int q=-1; int i; for(i=1;i<n;i++) q=max(q,p[i]+cut_rod(p,n-i)); return q; } int main() { int p[11]={0,1,5,8,9,10,17,17,20,24,30}; int i; for(i=0;i<11;i++) cout<<cut_rod(p,i+1)<<endl; }
运行结果：
使用动态规划方法求解最优钢条切割问题
动态规划有两种等价的实现方法，下面以钢条切割问题为例展示这两种方法。
第一种方法称为带备忘的自顶向下法。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。我们称这个递归过程是带备忘的，因为它“记住”了之前已经计算出的结果。
第二种方法称为自底向上法。这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序，按由小到大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已经求解完成。
下面给出的是自顶向下CUT-ROD过程的伪代码，加入了备忘机制：
MEMOIZED-CUT-ROD(p,n) let r[0...n] be a new array for i=0 to n r[i]=-∞ return MEMOIZED-CUT-ROD-AUX(p,n,r) MEMOIZED-CUT-ROD-AUX(p,n,r) if r[n]>=0 return r[i] if n==0 q=0 else q=-∞ for i=1 to n q=max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r)) r[n]=q return q
自底向上版本：
BOTTOM-UP-CUT-ROD(p,n) let r[0..n] be a new array r[0]=0 for j=1 to n q=-∞ for i=1 to j q=max(q,p[i]+r[j-i]) r[j]=q return r[n]
C++代码：
#include<iostream> using namespace std; int cut_rod(int p[],int n) { if(n==0) return 0; int q=-1; int i; for(i=1;i<=n;i++) q=max(q,p[i]+cut_rod(p,n-i)); return q; } //自顶向下 int memoized_cut_rod_aux(int p[],int n,int r[]) { int q=-1; int i; if(r[n]>=0) return r[n]; if(n==0) return 0; for(i=1;i<=n;i++) q=max(q,p[i]+memoized_cut_rod_aux(p,n-i,r)); r[n]=q; return q; } int memoized_cut_rod(int p[],int n) { int i; int r[n]; for(i=0;i<=n;i++) r[i]=-1; return memoized_cut_rod_aux(p,n,r); } //自底向上 int cutrod(int p[],int n) { int r[n]; int i,j; for(i=0;i<=n;i++) r[i]=0; int q; for(j=1;j<=n;j++) { q=-1; for(i=1;i<=j;i++) q=max(q,p[i]+r[j-i]); r[j]=q; } return r[n]; } int main() { int p[11]={0,1,5,8,9,10,17,17,20,24,30}; int i; cout<<"递归:"<<endl; for(i=0;i<11;i++) cout<<cut_rod(p,i)<<endl; cout<<"自顶向下："<<endl; for(i=0;i<11;i++) { cout<<memoized_cut_rod(p,i)<<endl; } cout<<"自底向上："<<endl; for(i=0;i<11;i++) { cout<<cutrod(p,i)<<endl; } }
运行结果：
