前言：动态规划的概念

　　动态规划（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 0q=-∞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 arrayfor 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=0else    q=-∞    for i=1 to n        q=max(q,p[i]+MEMOIZED-CUT-ROD-AUX(p,n-i,r))r[n]=qreturn q

自底向上版本：

BOTTOM-UP-CUT-ROD(p,n)let r[0..n] be a new arrayr[0]=0for j=1 to n    q=-∞    for i=1 to j        q=max(q,p[i]+r[j-i])    r[j]=qreturn r[n]

第十五章 动态规划——钢条切割