动态规划
钢条切割问题
Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。
钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。
来看一下其朴素递归如何实现：
实现原理：
/*************************************************************************
> File Name: 2.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月05日 星期日 23时09分32秒
************************************************************************/
#include<unistd.h>/*#包含<unistd.h>*/
#include<sys/types.h>/*#包含<sys/types.h>*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 99999999
using namespace std;
typedef long long ll;
int my_max(int x,int y){ return x>y?x:y; }
int CUT_ROD(int p[],int n);
int main(int argc,char *argv[])
{
int p[100]={0,1,5,8,9,10,17,17,20,24,30};//价格数组
int s;
s=CUT_ROD(p,40);//递归求解
printf("%d\n",s);//输出结果
return 0;
}
int CUT_ROD(int p[],int n)//大概思想，先确定左边要切割的大小，然后求右边的大小
{
if(n==0) return 0;//如果切割长度为0,则返回0值
int q=-INF;
for(int i=1;i<=n;i++)//左边切割的长度从1到n，然后求右边的大小
{
q=my_max(q,p[i]+CUT_ROD(p,n-i));//取各种状态的最优解
}
return q;
}朴素递归的缺点的要重复计算子问题，即子问题被重复计算了多遍。
经过分析，其计算次数为2的幂级量
那么下面用动态规划的方法解决该问题：
首先用一个数组来储存每个子问题的最优解，然后在要求子问题的时候先判断子问题是否求过了，如果求过了，就直接调用，否则进行计算，还要注意的一点是当其计算出一个子问题的最优解以后就把其保存在数组当中。
下面来看代码（只是稍微进行了一下变动）：
1.带备忘的自顶而下的方法：
/*************************************************************************
> File Name: 2.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月05日 星期日 23时09分32秒
************************************************************************/
#include<unistd.h>/*#包含<unistd.h>*/
#include<sys/types.h>/*#包含<sys/types.h>*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 99999999
using namespace std;
typedef long long ll;
int my_max(int x,int y){ return x>y?x:y; }
int MEMOZED_CUT_ROD_AUX(int p[],int n,int r[]);
int main(int argc,char *argv[])
{
int r[100];//这里的r[i]代表着其长度为i的刚条最优解
for(int i=0;i<100;i++) r[i]=-INF;
int p[100]={0,1,5,8,9,10,17,17,20,24,30};//价格数组
int s;
s=MEMOZED_CUT_ROD_AUX(p,20,r);//递归求解
printf("%d\n",s);//输出结果
return 0;
}
int MEMOZED_CUT_ROD_AUX(int p[],int n,int r[])//大概思想，先确定左边要切割的大小，然后求右边的大小
{
int q;
if(r[n]>=0) return r[n];
if(n==0) q=0;//如果切割长度为0,因为要对r[]数组赋值，所以给0；
else q=-INF;
for(int i=1;i<=n;i++)//左边切割的长度从1到n，然后求右边的大小
{
q=my_max(q,p[i]+MEMOZED_CUT_ROD_AUX(p,n-i,r));//取各种状态的最优解
}
r[n]=q;
return q;
}
这个与递归神似，就是加上了一个数组进行保存数据。
2.下面来看一个自底向上的方法，这个相对来说效率是比较高点的，
原理：这种方法一般需要恰当定义子问题的“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题求解，因而我们可以将子问题按规模大小进行排序，按由小到大的顺序进行求解，当求解某个子问题时，它所依赖的子问题都已经求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它时（也是第一次遇见它），它的所有前提子问题都已经求解完毕。
看完定义，来分析一下这道题目：
很显然，这道题按规模分类为钢条的长度，钢条长度大的数值求解时会用到钢条小的那个值，所以就先求规模小的，再求规模大的
来看代码：
/*************************************************************************
> File Name: 2.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月05日 星期日 23时09分32秒
************************************************************************/
#include<unistd.h>/*#包含<unistd.h>*/
#include<sys/types.h>/*#包含<sys/types.h>*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 99999999
using namespace std;
typedef long long ll;
int my_max(int x,int y){ return x>y?x:y; }
int BOTTOM_UP_CUT_ROD(int p[],int n);
int main(int argc,char *argv[])
{
int p[100]={0,1,5,8,9,10,17,17,20,24,30};//价格数组
int s;
s=BOTTOM_UP_CUT_ROD(p,20);//递归求解
printf("%d\n",s);//输出结果
return 0;
}
int BOTTOM_UP_CUT_ROD(int p[],int n)//大概思想，先确定左边要切割的大小，然后求右边的大小
{
int q;
int r[100];
memset(r,0,sizeof(r));
r[0]=0;//给最小规模的数据赋初值！！，这个在动态规划中常用
for(int i=1;i<=n;i++)//i大小代表其规模
{
q=-INF;
for(int j=1;j<=i;j++)//在求i规模的最优解时，会用到1-i规模的数据，所以说利用一个for循环求出一个最优解。
q=my_max(q,p[j]+r[i-j]);
r[i]=q;//求完后把值储存到r[]数组里面
}
return r[n];
}重构解：
现在只是知道了其最大值是多少，但并不知道具体怎么分，那么现在求解一下其具体怎么分
先直接上代码：
/*************************************************************************
> File Name: 2.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月05日 星期日 23时09分32秒
************************************************************************/
#include<unistd.h>/*#包含<unistd.h>*/
#include<sys/types.h>/*#包含<sys/types.h>*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 99999999
using namespace std;
typedef long long ll;
int my_max(int x,int y){ return x>y?x:y; }
int BOTTOM_UP_CUT_ROD(int p[],int n,int s[]);
void PRINT_CUT_ROD_SOLUSION(int s[],int n);//输出切割方案
int main(int argc,char *argv[])
{
int p[100]={0,1,5,8,9,10,17,17,20,24,30};//价格数组
int s[100];
int re;
int num;
num=7;
re=BOTTOM_UP_CUT_ROD(p,num,s);//递归求解
for(int i=0;i<=num;i++)
printf("%d ",s[i]);
printf("\nre=%d\n",re);//输出结果
PRINT_CUT_ROD_SOLUSION(s,num);//输出切割方案
return 0;
}
void PRINT_CUT_ROD_SOLUSION(int s[],int n)//原理：记录每一规模的选取的长度，然后进行由顶到底的递推
{
while(n!=0)
{
printf("%d ",s[n]);
n-=s[n];
}
}
int BOTTOM_UP_CUT_ROD(int p[],int n,int s[])//大概思想，先确定左边要切割的大小，然后求右边的大小
{
int q;
int r[100];
memset(r,0,sizeof(r));
r[0]=0;//给最小规模的数据赋初值！！，这个在动态规划中常用
for(int i=1;i<=n;i++)//i大小代表其规模
{
q=-INF;
for(int j=1;j<=i;j++)//在求i规模的最优解时，会用到1-i规模的数据，所以说利用一个for循环求出一个最优解。
{
if(p[j]+r[i-j]>q)//这里不用my_max()函数，是为了记录该规模下的切割长度
{
q=p[j]+r[i-j];
s[i]=j;//不断更新，并储存
}
}
r[i]=q;//求完后把值储存到r[]数组里面
}
return r[n];
}解决完这一道题
那么来总结一下：动态规划是一种自地向上的动态规划利用的是“逆拓扑序”思想，而带备忘的自顶而下的方式是利用“深度优先搜索”。
下面再举一个例子：
矩阵链乘法
矩阵链乘法问题可以表述如下：给定n个矩阵构成的一个链（A1*A2*A3……*An），其中i=1,2,……n,矩阵Ai的维数为p(i-1)*p(i),对于乘积A1*A2*A3……*An以一种最小化标量乘法次数的方式进行加括号。
所谓矩阵链乘法是指当一些矩阵相乘时，如何加括号来改变乘法顺序从而来降低乘法次数。
例如有三个矩阵连乘：A1*A2*A3，其维数分别为：10*100，100*5，5*50.如果按照（（A1*A2）*A3）来计算的话，求（A1*A2）要10*100*5=5000次乘法，再乘以A3需要10*5*50=2500次乘法，因此总共需要7500次乘法。如果按照（A1*（A2*A3））来计算的话，求（A2*A3）要100*5*50=25000次乘法，再乘以A1需要10*100*50=50000次乘法，因此总共需要75000次乘法。可见，按不同的顺序计算，代价相差很大
如果一个要遍历所有的括号的数量，则其是一个非常大的数量级，难以实现，下面利用动态规划的方法来解决这个问题。
给出应用动态规划的四个步骤：
1.刻画一个最优界的结构特征。
2.递归地定义最优解的值。
3.计算最优解的值，通常采用自底而上的方法。
4.利用计算出的信息构造一个最优解。
1.最优括号化方案的结构特征
在由i-j的序列中，存在一个最优解k,使得i-k与k-j组成的为乘积最小，然后再用同样的方案对i-k和k-j进行括号化。
即其原问题的括号化的方案就是其子问题的括号化方案，原问题和其子问题的求解形式一样。
然后利用最优子结构的性质从子问题的最优解构造出原问题的最优解，我们可以将问题划分为两个子问题，求出子问题实例的最优解，然后将子问题的最优解组合起来。我们必须保证在确定分割点时，已经考察了所有可能的划分点，这有就可以保证不会遗漏最优解。
2.一个递归求解方案
利用一个二维数组m[][]进行储存数据，m[i][j]代表着从i到j其最优解，则我们所要求的结果为m[1][n]，当i==j时 m[i][j]为0,
当i!=j时 m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
这个方程就叫做其状态转移方程。状态转移方程是动态规划中一个非常重要的元素，可以说是其核心，一般在写动态规划题目代码之前都会先写出其动规方程。
m[][]的值只保留了子问题最优解，但并未提供足够的信息来构造最优解。为此，我们用s[i][j]保存i-j 最优括号化方案的分割点位置k。
3.计算最优代价
递归算法会在递归调用数的不同分支中多次遇到同一个问题，这种问题的重叠性质的应用动态规划的另一个标识（第一个标识是最优子结构）
我们这次采用自底而上的表格法来代替备忘的自顶而下的方法。
来看具体代码：
/*************************************************************************
> File Name: juzhen.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月07日 星期二 19时15分45秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 9999999
using namespace std;
typedef long long ll;
void MATRIX_CHAIN_ORDER(int p[],int n,int s[][100],int m[][100]);
int main(int argc,char *argv[])
{
int p[100]={10,100,5,50};
int s[100][100],m[100][100];
int n=3;
//memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
memset(m,0,sizeof(m));
MATRIX_CHAIN_ORDER(p,n,s,m);
printf("%d\n",m[1][n]);
return 0;
}
void MATRIX_CHAIN_ORDER(int p[],int n,int s[][100],int m[][100])
{
int l,i,j,k,q;
for(i=1;i<=n;i++) m[i][i]=0;//长度为1的值赋0;
for(l=2;l<=n;l++)//l代表其长度，即规模大小，规模大小由小到大
{
for(i=1;i<=n-l+1;i++)//i的一个for循环遍历了所有的长度为l的链
{
j=i+l-1;//i-j链的长度为l
m[i][j]=INF;//先赋负值
for(k=i;k<=j-1;k++)//判断从那个部分分割为最优解，这里一定要注意边界条件
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//计算值
//printf("%d %d",p[k],k);
if(m[i][j]>q)
{
m[i][j]=q;//判断并更新其值
s[i][j]=k;//更新并储存分割点
}
}
}
}
}在注释中已经进行了些解释，这里我再来进行解释一下：
在计算长度l的数列时就已经计算过小于l的数列，即计算当前步的时候依赖于已经计算过的数值。
其计算的过程其实可以看作一个往表里面填数的过程。
来看这个6长度矩阵链的例子
A1 30 × 35 A2 35 × 15 A3 15 × 5 A4 5 × 10 A5 10 × 20 A6 20 × 25
这个表的i轴代表起始，j代表末尾，计算从左下角的向右，从最下端依次向上，在计算一个点时，会用到其左下列和右下列，而这些数都已经计算出来了。
经过分析算法可得，其时间复杂度为n^3还需要n^2的空间来保存链表。相对穷举高效的多。
那现在来到了第四步
4.构造最优解
与钢条切割方式类似，其构造最优解时也是利用了，自顶而下的递归方式，
就是先求规模最大的链，然后根据结果求规模小一点的链，最后直到单个就输出。（注意其中括号的运用）
/*************************************************************************
> File Name: juzhen.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月07日 星期二 19时15分45秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 9999999
using namespace std;
typedef long long ll;
void MATRIX_CHAIN_ORDER(int p[],int n,int s[][100],int m[][100]);
void PRINT_OPTIMAL_PARENS(int s[][100],int i,int j);
int main(int argc,char *argv[])
{
int p[100]={30,35,15,5,10,20,25};
int s[100][100],m[100][100];
int n=6;
//memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
memset(m,0,sizeof(m));
MATRIX_CHAIN_ORDER(p,n,s,m);
printf("%d\n",m[1][n]);
PRINT_OPTIMAL_PARENS(s,1,n);
return 0;
}
void PRINT_OPTIMAL_PARENS(int s[][100],int i,int j)
{
if(i==j)
printf("A[%d]",i);
else
{
printf("(");
PRINT_OPTIMAL_PARENS(s,i,s[i][j]);
PRINT_OPTIMAL_PARENS(s,s[i][j]+1,j);
printf(")");
}
}
void MATRIX_CHAIN_ORDER(int p[],int n,int s[][100],int m[][100])
{
int l,i,j,k,q;
for(i=1;i<=n;i++) m[i][i]=0;//长度为1的值赋0;
for(l=2;l<=n;l++)//l代表其长度，即规模大小，规模大小由小到大
{
for(i=1;i<=n-l+1;i++)//i的一个for循环遍历了所有的长度为l的链
{
j=i+l-1;//i-j链的长度为l
m[i][j]=INF;//先赋负值
for(k=i;k<=j-1;k++)//判断从那个部分分割为最优解，这里一定要注意边界条件
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//计算值
//printf("%d %d",p[k],k);
if(m[i][j]>q)
{
m[i][j]=q;//判断并更新其值
s[i][j]=k;//更新并储存分割点
}
}
}
}
}到这里，我们已经利用动态规划解决了两个问题，我们在来详细了解一下动态规划的原理：
动态规划原理
最优子结构
如果一个问题的最优解包含了其子问题的最优解，我们就称此子问题具有最优子结构。
最优子结构在贪心算法中和动态规划算法中体现较多，在动态规划中，我们用子问题的最优解来构造原问题的最优解，因此我们必须小心确保考察了最优解中用到的所有子问题（只有这样才能算当前最优）
前面两个例子都用到了最优子结构问题，
你会发现在发掘最优子结构性质的过程中，实际上遵循如下模式：
1.证明最优解的第一个组成部分是做出一个选择，做出这个选择会产生一个或多个子问题。
2.对于一个给定的问题，在其可能的一步选择中，你只是假定已经知道了这个选择（通过max 或min遍历）
3.给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何更好的刻画子问题空间。
4.作为构成原问题的最优解组成部分，每个子问题的解就是它本身的最优解。
刻画子问题空间的好经验是：保持子问题空间（就是用来储存最优解的“数组”）尽可能简单，只有在必要的时候才扩展它。例如在钢条切割问题，子问题空间中包含的问题为：对于每个i值，长度为i的钢条的最优切割问题。而对于矩阵链乘法，其子问题涉及到里两个变化的量i和j分别代表两端，所以其子问题空间需要一个二维数组。
对于不同问题的领域，最优子结构的不同体现在两个方面：
1.原问题的最优解中涉及多少个子问题
2.在确定最优解使用哪些子问题时，我们需要考察多少种选择。
在钢条切割中，长度为n的钢条的最优切割问题仅仅涉及一个子问题（长度为n-i的钢条的最优切割），需要考察n种情况，而对于矩阵链乘法，最优解i-j需要使用两个子问题，考察j-i种情况，我们可以用子问题的总数和每个子问题需要考察多少种选择这两个因素的乘积来粗略分析动态规划算法的运行时间，对于钢条切割问题一共有n个子问题，每个问题最多要考察n种选择，因此运行时间为n*n，而矩阵链乘法有n*n个子问题，每个问题需要考察n-1个选择，因此运行时间为n*n*n。
在动态规划方法中，我们通常自底向上地使用最优子结构，首先求得子问题的最优解，然后求得原问题的最优解，在此过程中，我们通过选择，选择出能得到原问题最优解的子问题。
原问题最优解的代价通常就是子问题最优解的代价在加上由此次选择直接产生的代价。例如在刚条切割 问题中，此处的代价就是p[i] ，而对于矩阵链乘法，此次选择的代价为p[i-1]*p[k]*p[j]。
这里顺便提及一下贪心算法，它与动态规划有很多相似之处，特别是，能够应用贪心算法的问题也具有最优字结构性质，贪心算法和动态规划最大的不同在于，它并不是首先寻找子问题的最优解，然后在其中选择，而是首先做出一次“贪心选择”——在局部看起来最优的选择——然后求解选出的子问题，从而不用求解那些用不到的子问题，这样的策略在某种情况下也能够得到最优解。
在使用动态规划的方法中要注意问题是否有最优子结构性质。
来看下面两个例子：
无权最短路径和无权最长路径，事实上，无权最短路径有最优子结构，而无权最长路径没有最优子结构。
对于该类问题，原问题包括两个子问题，每一个子问题都有最优解，如果要满足最优子结构性质，需要满足两个子问题的解的组合产生一条简单路径。也就是说两个子问题的最优解中不能包含相同的节点（求解一个子问题时用到了某些资源，导致这些资源在求解其他子问题时不可用）。
先来解释为什么无权最长路径没有最优子结构：
举个例子，对于一个环状的路径，其两个子问题的最优解会包含相同的节点（这种情况称为两个最长简单路径的子问题的相关的），即这就与上述判断矛盾，所以说无权最长路径问题没有最优子结构。
而对于无权最短路径，则存在最优子结构。因为对于原问题的两个子问题，其最优解不会包含相同的节点，则就不会造成资源的冲突，这种情况，我们可以保证最短路径问题的子问题间是无关的。这样其具有最优子结构性质，例如上面提到的矩阵链乘法，两个子链是互不相交的，因此任何矩阵都不会同时包含在两条子链中。所以其具有子问题的无关性质。而在钢条切割问题中，为了确定长度为n的钢条的最优切割方案，其只有一个子问题，所以其子问题的无关性显然是可以保证的。
重叠子问题
适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须满足足够“小”，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。一般来讲，不同问题的总数通常是输入规模的多项式函数为好。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。与之相对，适合用分治方法求解的问题通常在递归的每一步都生成全新的子问题。动态规划算法通常利用重叠子问题性质，对每个子问题求解一次，经解存入一个表中，当再次需要这个子问题时直接查表，每次查表的代价为时间常量。
为了详细说明重叠子问题性质，重新考察一下矩阵链乘法问题给出其递归代码：
/*************************************************************************
> File Name: juzhen.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月07日 星期二 19时15分45秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 9999999
using namespace std;
typedef long long ll;
int RECURSIVE_MATRIX_CHAIN(int s[][100],int m[][100],int p[],int i,int j);
void MATRIX_CHAIN_ORDER(int p[],int n,int s[][100],int m[][100]);
void PRINT_OPTIMAL_PARENS(int s[][100],int i,int j);
int main(int argc,char *argv[])
{
int p[100]={30,35,15,5,10,20,25};
int s[100][100],m[100][100];
int n=6;
//memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
memset(m,0,sizeof(m));
// MATRIX_CHAIN_ORDER(p,n,s,m);
RECURSIVE_MATRIX_CHAIN(s,m,p,1,n);
printf("%d\n",m[1][n]);
PRINT_OPTIMAL_PARENS(s,1,n);
return 0;
}
void PRINT_OPTIMAL_PARENS(int s[][100],int i,int j)
{
if(i==j)
printf("A[%d]",i);
else
{
printf("(");
PRINT_OPTIMAL_PARENS(s,i,s[i][j]);
PRINT_OPTIMAL_PARENS(s,s[i][j]+1,j);
printf(")");
}
}
void MATRIX_CHAIN_ORDER(int p[],int n,int s[][100],int m[][100])
{
int l,i,j,k,q;
for(i=1;i<=n;i++) m[i][i]=0;//长度为1的值赋0;
for(l=2;l<=n;l++)//l代表其长度，即规模大小，规模大小由小到大
{
for(i=1;i<=n-l+1;i++)//i的一个for循环遍历了所有的长度为l的链
{
j=i+l-1;//i-j链的长度为l
m[i][j]=INF;//先赋负值
for(k=i;k<=j-1;k++)//判断从那个部分分割为最优解，这里一定要注意边界条件
{
q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];//计算值
//printf("%d %d",p[k],k);
if(m[i][j]>q)
{
m[i][j]=q;//判断并更新其值
s[i][j]=k;//更新并储存分割点
}
}
}
}
}
int RECURSIVE_MATRIX_CHAIN(int s[][100],int m[][100],int p[],int i,int j)//递归代码
{
int q;
if(i==j) return 0;
m[i][j]=INF;
for(int k=i;k<=j-1;k++)
{
q=RECURSIVE_MATRIX_CHAIN(s,m,p,i,k)+
RECURSIVE_MATRIX_CHAIN(s,m,p,k+1,j)
+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
return m[i][j];
}
来给出其递归调用图：
从图中可以看出许多子问题被重复计算了多遍，其过程计算m[1,n]的时间至少是n的指数函数（利用数学对归纳法证明），这就总结出：凡是一个问题的自然递归算法的递归调用树中反复出现相同的子问题，而不同的子问题的总数很少时，动态规划方法都能提高效率。
重构最优解
从实际考虑，我们通常将每个子问题所做的选择存在一个表中，这样就不必根据代价值来重构这些信息。对于矩阵链乘法，如果用s[i][j]记录了子问题的最优代价，其重构每次选择只需O(1)，否则其需要w(1)时间。
备忘
思路就是对自然但低效的递归算法加入备忘机制。与自底而上方法一样，我们维护一个表记录子问题的解，但仍保持递归算法的控制流程。
带备忘的递归算法为每个子问题维护一个表项来保存它的解。每个表项的初值设为一个特殊值，表示尚未填入子问题的解。当递归调用过程中第一次遇到子问题时，计算其解，并存入表项。随后每次遇到同一个子问题，只是简单的查表，返回其解。
下面给出矩阵相乘的带备忘的自顶而下的版本：
/*************************************************************************
> File Name: juzhen.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月07日 星期二 19时15分45秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 9999999
using namespace std;
typedef long long ll;
int MEMOSIZED_MAXTRIX_CHAIN(int s[][100],int m[][100],int p[],int n);
int LOOKUP_CHAIN(int s[][100],int m[][100],int p[],int i,int j);
void PRINT_OPTIMAL_PARENS(int s[][100],int i,int j);
int main(int argc,char *argv[])
{
int p[100]={30,35,15,5,10,20,25};
int s[100][100],m[100][100];
int n=6;
int re;
memset(s,0,sizeof(s));
memset(m,0,sizeof(m));
re=MEMOSIZED_MAXTRIX_CHAIN(s,m,p,n);
printf("%d\n",m[1][n]);
PRINT_OPTIMAL_PARENS(s,1,n);
return 0;
}
void PRINT_OPTIMAL_PARENS(int s[][100],int i,int j)
{
if(i==j)
printf("A[%d]",i);
else
{
printf("(");
PRINT_OPTIMAL_PARENS(s,i,s[i][j]);
PRINT_OPTIMAL_PARENS(s,s[i][j]+1,j);
printf(")");
}
}
int MEMOSIZED_MAXTRIX_CHAIN(int s[][100],int m[][100],int p[],int n)
{
for(int k=1;k<=n;k++)
for(int l=1;l<=n;l++)
m[k][l]=INF;//每个表项被初始化为正无穷，表示还未存入过值
return LOOKUP_CHAIN(s,m,p,1,n);
}
int LOOKUP_CHAIN(int s[][100],int m[][100],int p[],int i,int j)
{
int q;
if(m[i][j]<INF)//如果该子问题已经被计算过，直接返回。
return m[i][j];
if(i==j)
m[i][j]=0;//只有一个时为0
else
{
for(int k=i;k<=j-1;k++)
{
q=LOOKUP_CHAIN(s,m,p,i,k)+
LOOKUP_CHAIN(s,m,p,k+1,j)+p[i-1]*p[k]*p[j];
if(q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
return m[i][j];
}备忘时，阴影子树表示的那些直接查表获得而非重新计算得到。
通常情况下，如果每个子问题都必须求解一次，自底向上动态规划算法会必自顶向下备忘算法快，(差了以个常量系数)，因为自底向上算法没有递归调用的开销，表的维护开销也更小。而且对于某些问题，我们可以利用表的访问模式来进一步降低时空代价(就比如某些可以用滚动数组)。相反如果子问题空间中某些子问题完全不必求解，备忘方法就会体现出优势了，因为它只会求解那些必要的子问题。
经过上面的介绍，大家应该对动态规划有了一个基本的了解，下面按照以上的步骤，介绍几个经典的例题：
最长公共子序列
问题介绍：给定两个序列X={x[1],x[2],x[3],x[4]......x[m]},和Y={y[1],y[2],y[3],y[4],y[5]....y[n]}.求X和Y长度最长的公共子序列。简称LCS
步骤1：刻画最长的公共子序列的特征
最长公共子序列的结构有如下表示：
设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>，则：
- 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
- 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
- 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。
由此可以看出其具有最优子结构，因为每个原问题的最优解都包含着子问题的最优解。
步骤2：一个递归解
分析过其最优子结构，可以看出其有重叠子问题性质。
与矩阵链乘法相似，设计LCS问题的递归算法首先要建立最优解的递归式。我们定义c[i][j]为X[i]和Y[j]的LCS的长度，根据LCS问题的最优子结构性质可得：
c[i][j]=0 i=0或j=0
c[i][j]=c[i-1][j-1] +1 i,j>0 且 X[i]=Y[j]
c[i][j]=max(c[i][j-1],c[i-1][j]) i,j>0 且 X[i]!=Y[j]
观察到递归公式中，通过限制条件限定了需要求解哪些子问题。这是LCS问题通过动态规划解决的一个新特性。
该问题采用自底而上的算法进行计算，先用一个表c[][]来保存每个子问题的值（即LCS长度），再用一个b[][]来保存每个子问题所选择的最优解。那么来确定计算次序，由步骤二的递推公式可以看出，当计算一个原问题时，其子问题是对应表格中左上角方向相邻的数，所以我们按行主次序，先从第一行进行计算，从上到下，从左到右。
下面上代码：
/*************************************************************************
> File Name: LCS.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月13日 星期一 17时57分15秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF (1ll<<60)-1
using namespace std;
typedef long long ll;
void LCS_LENGTH(int x[],int y[],int c[][100],int b[][100],int m,int n);
void PRINT_LCS(int b[][100],int x[],int i,int j);
int main(int argc,char *argv[])
{
int x[100]={0,1,2,3,2,4,1,2};
int y[100]={0,2,4,3,1,2,1};
int c[100][100];
int b[100][100];
int m=7;
int n=6;
memset(c,0,sizeof(c));
memset(b,0,sizeof(b));
LCS_LENGTH(x,y,c,b,m,n);//自底而上求解
PRINT_LCS(b,x,m,n);//构造CLS
/*************输出两个二维数组供理解***************/
/*printf("\n");
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",c[i][j]);
}
printf("\n");
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",b[i][j]);
}
printf("\n");
}*/
return 0;
}
void LCS_LENGTH(int x[],int y[],int c[][100],int b[][100],int m,int n)
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=0;//0代表左上
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=1;//1代表上
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=-1;//-1代表左
}
}
}
}
void PRINT_LCS(int b[][100],int x[],int i,int j)//从最后一个开始进行，根据b数组向上寻找
{
if(i==0||j==0) return;
if(b[i][j]==0)
{
PRINT_LCS(b,x,i-1,j-1);//如果为左上，则输出
printf("%d ",x[i]);
}
else if(b[i][j]==1) //否则，根据方向寻找
PRINT_LCS(b,x,i-1,j);
else
PRINT_LCS(b,x,i,j-1);
}步骤4：构造最优解
下面这个图就大概解释了怎样构造最优解，从最后一个开始，寻找最优解，该代码已经放在上面程序中，并且已经写上注释，这里不再赘述。
算法改进：
1.去掉表b，在O(1)时间内判断其使用了哪一个值。
2.利用滚动数组进行计算，保留表b
看一下改进2的代码：
/*************************************************************************
> File Name: LCS.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月13日 星期一 17时57分15秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF (1ll<<60)-1
using namespace std;
typedef long long ll;
void LCS_LENGTH(int x[],int y[],int c[][100],int b[][100],int m,int n);
void PRINT_LCS(int b[][100],int x[],int i,int j);
int main(int argc,char *argv[])
{
int x[100]={0,1,2,3,2,4,1,2};
int y[100]={0,2,4,3,1,2,1};
int c[2][100];
int b[100][100];
int m=7;
int n=6;
memset(c,0,sizeof(c));
memset(b,0,sizeof(b));
LCS_LENGTH(x,y,c,b,m,n);//自底而上求解
PRINT_LCS(b,x,m,n);//构造CLS
/*************输出两个二维数组供理解***************/
/*printf("\n");
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",c[i][j]);
}
printf("\n");
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",b[i][j]);
}
printf("\n");
}*/
return 0;
}
void LCS_LENGTH(int x[],int y[],int c[][100],int b[][100],int m,int n)
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(x[i]==y[j])//改进的地方：二维数组c行下标统一对2取余。
{
c[i%2][j]=c[(i-1)%2][j-1]+1;
b[i][j]=0;//0代表左上
}
else if(c[(i-1)%2][j]>=c[i%2][j-1])
{
c[i%2][j]=c[(i-1)%2][j];
b[i][j]=1;//1代表上
}
else
{
c[i%2][j]=c[i%2][j-1];
b[i][j]=-1;//-1代表左
}
}
}
}
void PRINT_LCS(int b[][100],int x[],int i,int j)//从最后一个开始进行，根据b数组向上寻找
{
if(i==0||j==0) return;
if(b[i][j]==0)
{
PRINT_LCS(b,x,i-1,j-1);//如果为左上，则输出
printf("%d ",x[i]);
}
else if(b[i][j]==1) //否则，根据方向寻找
PRINT_LCS(b,x,i-1,j);
else
PRINT_LCS(b,x,i,j-1);
}
到这里，这一道题就基本上完成了。
总结一下：
首先判断这个问题有么有最优子结构，有没有重叠子问题，然后判断其可不可以用动态规划求解，如果可以写出其最优解的递归式(也称状态转移方程)，然后在其子问题空间中计算值，最后构造出最优解。
该问题最主要的地方是判断最优子结构和写出状态转移方程。
图论的最短路径算法：Floy算法
对于图的最短路径，在上文中也提过，其具有最优子结构特征，下面跟据4个步骤，来分析此问题
步骤1：最短路径的最优子结构特征
我们先对图中每个节点进行编号，并且利用e[][]保存最优值,n代表其节点总数。在求i到j的的最短距离e[i][j]时，假设其经过节点k(1<k<n)，则原问题就可以产生两个子问题，这两个子问题分别为i到k的最短距离e[i][k]和k到j的最短距离e[k][j]，原问题的解就等于两个子问题的解的和(即e[i][j]=e[i][k]+e[k][j])，所以现在就可以判断其具有最优子结构性质，而且还具有重叠子问题性质。
步骤2.：一个递归式
根据步骤1的判断，我们可以在其经过中间节点k的所有情况中找到最小值，作为原问题的解
则这个递归式可以表示为 :
e[i][j]=min(e[i][k]+e[k][j]) (1<k<n)
注意：k的范围与矩阵链乘法的不一样，因为这里的节点没有大小，位置限制。
步骤3：计算最短路径
这里的规模为其经过的节点数，所以我们从规模小到规模大计算。
下面给出代码：
/*************************************************************************
> File Name: floy.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月13日 星期一 21时45分41秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 999999
using namespace std;
typedef long long ll;
int main(int argc,char *argv[])
{
int e[100][100];
int n,m,x,y,v;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)//利用邻接矩阵储存图
for(int j=1;j<=n;j++)
{
if(i==j) e[i][j]=0;
else e[i][j]=INF;
}
for(int i=1;i<=m;i++)//录入单向边
{
scanf("%d %d %d",&x,&y,&v);
e[x][y]=v;
}
//k代表其规模(中间节点数)，其规模由小到大
//(注意，这里其循环次数代表其规模，而不k的值
//k的值只是代表了在规模为特定值时其必须要经过的点)，
//除了代表其规模外，其还指定了其必须经过节点，这就是floy算法的精华所在！！
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)//遍历所有可能情况
{
for(int j=1;j<=n;j++)
{
if(e[i][k]+e[k][j]<e[i][j])
e[i][j]=e[i][k]+e[k][j];
}
}
}
for(int i=1;i<=n;i++)//打印最短路径
{
for(int j=1;j<=n;j++)
{
printf("%6d ",e[i][j]);
}
printf("\n");
}
return 0;
}
测试数据：
5 7 //5个顶点，7条边
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
其中对k的利用是floy算法的精华部分，到这里其最短路径就被计算出来了。
经典问题：石子归并
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
下面按照4个步骤来分析这个问题：
步骤1：石子归并的最优子结构特征
由原问题知，对于一个原i-j的最优解，其可以通过求i-k和k-j两个子问题的最优解来求得。而且求解原问题的方案与求解其子问题的方案相同。这就表明了其具有最优子结构特征。
步骤2：一个递归式
利用二维数组m[][]，来储存其最小代价，利用s[][]保存其最优解，c[i]来储存前i个数的和。
则跟据题意可得对于从i到j的最小代价m[i][j]，等于从i到k的最小代价m[i][k]加上从k到j的最小代价m[k][j]在加上本次和并的代价 c[j]-c[i] 即：
m[i][j]=max(m[i][k]+m[k][j])+c[j]-c[i] (i<k<j)
步骤3：求解其最小代价
与矩阵链乘法类似，这里的规模为已经和并的石子的数目，我们采用自底向上的方法求解，由递归式可以看出，规模大的要利用到规模小的数，所以要下计算规模小的数。确定了计算顺序，上代码：
/*************************************************************************
> File Name: shizi.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月14日 星期二 10时16分43秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 99999999
using namespace std;
typedef long long ll;
void SHIZI_WIEGHT(int n,int s[][100],int m[][100],int c[]);
void PRINT_CHAIN(int s[][100],int i,int j,int w[]);
int main(int argc,char *argv[])
{
int m[100][100];
int s[100][100];
int c[100];
int w[100];
int n;
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
memset(c,0,sizeof(c));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
c[i]=c[i-1]+w[i];
SHIZI_WIEGHT(n,s,m,c);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",s[i][j]);
}
printf("\n");
}
printf("%d\n",m[1][n]);
PRINT_CHAIN(s,1,n,w);
return 0;
}
void SHIZI_WIEGHT(int n,int s[][100],int m[][100],int c[])
{
for(int num=2;num<=n;num++)//num代表其规模，其规模由小到大
{
for(int i=1;i<=n-num+1;i++)
{
int j=i+num-1;
m[i][j]=INF;
for(int k=i;k<j;k++)
{
int p=m[i][k]+m[k+1][j]+c[j]-c[i-1];
if(p<m[i][j])
{
m[i][j]=p;
s[i][j]=k;
}
}
}
}
}
void PRINT_CHAIN(int s[][100],int i,int j,int w[])
{
if(i==j)
{
printf(" %d ",w[i]);
return ;
}
else
{
printf("(");
PRINT_CHAIN(s,i,s[i][j],w);
PRINT_CHAIN(s,s[i][j]+1,j,w);
printf(")");
}
}测试数据：
4
4 1 1 4
运行结果： 18 (4 ((1 1) 4) )
步骤4：构造最优解
根据由顶到下的原理，进行构造最优解，利用递归方式。代码已经放在上方，原理与矩阵链乘法类似。
经典问题：0-1背包
问题描述：
有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大 (每种物品只有一件，可以选择放或者不放)。
步骤1: 0-1背包的最优子结构特征
经分析，每个物品只有两种状态，放进去或不放进去，我们构造一个二维的子问题空间。
我们利用一个二维数组m[][],m[i][j]代表了前i个背包在背包的容量为j的情况下的最大容量。
对于前n个物品，背包容量为c 这个原问题，可以产生一个子问题，当第n个物品放入背包中时，
其为求解前n-1个物品，背包容量为c-v[n] 子问题m[n-1][c-v[n]]，如果第n个物品不放入背包中时。
其原问题m[n][c]的解等于其子问题m[n-1][c]的解。而且求解子问题的方案等同与求解原问题的方案。
所以经过判断其有最优子结构特征和重叠子问题特征。
步骤2：一个递归式
跟据步骤1的分析，易看出，其分两种情况：放与不放。我们取其最大价值。
则该递归式可以表示为：
m[i][j]=max(m[i-1][j],m[i-1][j-v[i]]+w[j])
步骤3：求解其最大价值
我们仍然采用自底而上的方法计算，该问题的规模为物品的个数和其背包的容量，
由于规模较大的问题要用到规模较小的问题，所以先计算规模较小的问题，
然后根据规模较小的问题计算规模较大的问题，我们按主次序计算，既从上到下，从左到右计算。
下面上代码：
/*************************************************************************
> File Name: 0-1bag.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月13日 星期二 21时45分41秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 999999
using namespace std;
typedef long long ll;
int my_max(int x,int y) { return x>y?x:y; }
int main(int argc,char *argv[])
{
int v[100];
int w[100];
int m[100][100];
int N,V;
memset(v,0,sizeof(v));
memset(w,0,sizeof(w));
memset(m,0,sizeof(m));
scanf("%d %d",&N,&V);
for(int i=1;i<=N;i++)
scanf("%d",&v[i]);
for(int j=1;j<=N;j++)
scanf("%d",&w[j]);
for(int i=1;i<=N;i++)
{
for(int j=v[i];j<=V;j++)//直接从v[i]开始（因为j-v[i]>=0），降低复杂度
{
m[i][j]=my_max(m[i-1][j],m[i-1][j-v[i]]+w[i]);
}
}
printf("%d\n",m[N][V]);
return 0;
}
测试用例：
结果：
54
步骤4：构造最优解
/*************************************************************************
> File Name: 0-1bag.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月13日 星期二 21时45分41秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define INF 999999
using namespace std;
typedef long long ll;
int my_max(int x,int y) { return x>y?x:y; }
void findpath(int s[],int m[][100],int v[],int w[],int N,int V);
int main(int argc,char *argv[])
{
int v[100];
int w[100];
int m[100][100];
int s[100];
int N,V;
memset(v,0,sizeof(v));
memset(w,0,sizeof(w));
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
scanf("%d %d",&N,&V);
for(int i=1;i<=N;i++)
scanf("%d",&v[i]);
for(int j=1;j<=N;j++)
scanf("%d",&w[j]);
for(int i=1;i<=N;i++)
{
for(int j=v[i];j<=V;j++)//直接从v[i]开始（因为j-v[i]>=0），降低复杂度
{
m[i][j]=my_max(m[i-1][j],m[i-1][j-v[i]]+w[i]);
}
}
findpath(s,m,v,w,N,V);
printf("%d\n",m[N][V]);
/*for(int i=1;i<=N;i++)
{
for(int j=1;j<=V;j++)
{
printf("%3d ",m[i][j]);
}
printf("\n");
}*/
for(int i=1;i<=N;i++) printf("%d ",s[i]);
return 0;
}
void findpath(int s[],int m[][100],int v[],int w[],int N,int V)
{
int x=V;
for(int i=N;i>=2;i--)//从最后一行开始遍历，判断其与上方的那个数是否相同
{
if(m[i][x]==m[i-1][x])//如果相同，则该数没有被放入背包，赋0值
s[i]=0;
else//如果不相同，则该数被放入背包中，赋1值
{
s[i]=1;
x-=v[i];
}
}
}
根据其求解时的两种不同情况，可以从顶而小求解其最优解。