动态规划问题同分治策略一致，都是将大问题划分为若干小问题
而动态规划问题将问题分解为不是相互独立的子问题，利用这一特点，用一个表来记录所有已经解决子问题的答案，不管该子问题以后是否被用到，只要被计算过，就将其结果填入表中
动态规划基本要素
- 最优子结构：整体问题的最优解包含子问题的最优解
- 重叠子问题：有些子问题被反复计算多次
- 备忘录方法：为了避免重复求解，建立备忘录存储已经求解过的问题结果
1.矩阵连乘问题
给定n个矩阵{A1,A2,A3,...,AN}，考察这n个矩阵的乘积
A1A2A3...An
由于矩阵乘法满足结合率，故矩阵连乘有多种计算次序，这种计算次序可以用加括号的方式来确定
方法一：穷举法
列出所有可能的计算次序，并计算出每一种计算次序相应的数乘次数
方法二：动态规划
将矩阵连乘积 AiA(i+1)A(i+2)...A(j)记为A[i:j]，考察其最优计算次序，从k处断开，那么计算量为
先从小问题的计算开始，每一步均选出子问题的最优解，最终得到问题的最优解
可以看到计算次序为<1,2>,<1,3>...<1,3>,<2,4>...<4,6>,<1,4>... 这样进行计算的
例子
针对上述矩阵的最优解
m[i][j]表示每个子问题的最优解，s[i][j]表示每次问题选择断点k，然后两部分计算如下
void MatrixChain(int *p，int n，int **m，int **s){for (int i = 1; i <= n; i++) m[i][i] = 0;//自己到自己代价为0for (int r = 2; r <= n; r++)//每个斜线的循环，共画出n-1条（去掉了对角线）for (int i = 1; i <= n –(r-1); i++)//每次的乘法计算循环，最开始的时候为n-1次然后次数越来越少{int j=i+r-1;m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];s[i][j] = i; //记录最少乘法的位置for (int k = i+1; k < j; k++) {int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}}
}输出最优计算次序
public static void TraceBack (int [][]s，int i，int j)
{if (i==j) return;TraceBack(s, i, s[i][j]);TarceBack(s,s[i][j]+1,j);System.out.println(“Multiply A”+i+”,”+s[i][j]+”and A”+(s[i][j]+1)+”,”+j);
}
2.最长公共子序列
若给定序列 X = {X1,X2,...,Xm} 则Z为X的子序列是指存在一个严格递增的下标序列使得对于所有的j = 1，2，3...，k 均存在Zj = Xij
例子：序列Z={B，C，D，B}是序列X={A，B，C，B， D，A，B}的子序列，相应的递增下标序列为{2，3，5， 7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是 Y的子序列时，称Z是序列X和Y的公共子序列。
目标：找出X和Y的最长公共子序列
设序列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的最长公共子序列。
n，m，k是序列长度，而减去1表示去掉最后一个元素
对于上述性质1，在直到最后一个公共元素是zk的时候，去掉三个序列中的该元素，那么就可以知道最长公共子序列
对于性质2，如果xm不是最后一个公共子元素，去掉无影响，性质三同理
得到如下递归公式
用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。
第三个递推代表着如果xi不等于yj的时候，看看哪一个序列减去之后最长子序列长度会不变，当减到xi = yj的时候，长度加一，index均减一，继续递归
void LCSLength(int m，int n，char *x，char *y，int **c，int **b)
{int i，j;for (i = 1; i <= m; i++) c[i][0] = 0;for (i = 1; i <= n; i++) c[0][i] = 0;//当两个子序列其中一个长度为0的时候，最长子序列长度为0for (i = 1; i <= m; i++)for (j = 1; j <= n; j++) {if (x[i]==y[j]) {c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}//使用b[i][j]来标记三种情况else if (c[i-1][j]>=c[i][j-1]) {c[i][j]=c[i-1][j]; b[i][j]=2;}else { c[i][j]=c[i][j-1]; b[i][j]=3; }}
}note:这里解释一下三种个情况，分别为最后一位相等，X序列的最后一位是公共子序列，Y序列的最后一位是公共子序列void LCS(int i，int j，char *x，int **b)
{if (i ==0 || j==0) return;if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; }//情况一：两者相等else if (b[i][j]== 2) LCS(i-1，j，x，b);//情况二：Y序列最后一位是公共子序列else LCS(i，j-1，x，b);//情况三：X序列的最后一位是公共子序列
}改进：省去数组b，由c[i-1][j-1]，c[i-1][j]和c[i][j-1]来确定c[i][j]
如果只需要计算最长公共子序列的长度，在计算c[i][j]时，只用到数组c的第i行和 第i-1行。
3.最大子段和
给定n个整数（可能为负）组成的序列a1 a2…an，求从i加到j的字段和最大值，即ai ,ai+1,…,aj整数之和的最大 值。
note：当所有整数均为负数的时候，最大子段和为0
例：序列（-2,11,-4,13,-5,-2)的最大子段和为20.
动态规划算法：时间复杂度O(n)
算法原理：定义变量b存储到达下标j的最大字段和，而b[j+1] = b[j]+a[j+1],如果b[j]>=0，否则等于a[j+1]即可
int MaxSum(int n,int *){int sum = 0;int b = 0;for(int i=1;i<=n;i++){if(b>=0) b+=a[i];else b=a[i];if (b>sum) sum=b;//最优解}return sum;
}4.凸多边形最优剖分（较为抽象）
用多边形顶点的逆时针序列表示凸多边形，即：P={v0,v1,…,vn-1}
若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦 将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。
多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。
在有 n个顶点的凸多边形的三角剖分中，恰有n-3条弦和n-2个三角形。
最优三角剖分问题：给定凸多边形P，以及定义在由多边形的边和弦组成的 三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分 中诸三角形上权之和为最小。
凸多边形的三角剖分与表达式的完全加括号有紧密联系。完全加括号的矩阵连乘积所相应的语法树如图 (a)所示。凸多边形的三角剖分也可以用语法树表示。
矩阵连 乘积中的每个矩阵Ai对应 于凸(n+1)边形中的一条 边vi-1vi。三角剖分中的 一条弦vivj(i<j)对应矩阵连乘积A[i+1:j]
做法：对给定矩阵链A1A2 …An，定义凸(n+1)边形 P=(v0v1 …vn) ，使得矩阵Ai与凸(n+1)边形中的一条边vi-1vi一一对应。若Ai的维数为pi-1*pj，则定义三角形vivjvk权 函数w(vivjvk)=pipjpk,依此权函数的定义，凸多边形P的最 优三角剖分所对应的语法树给出矩阵链的最优完全加括号 方式。
定义t[i][j]，1≤i<j≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值
递归函数如下：同矩阵连乘问题
#include "stdafx.h"
#include <stdio.h>
#define N 6 //顶点数/边数
int weight[][N] =
{{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0
}};//权值矩阵，每个点的值代表维度，拆分时线和括号等价
int t[N][N]; //t[i][j]表示多边形{Vi-1 Vk Vj}的最优权值
int s[N][N]; //s[i][j]记录Vi-1到Vj最优三角剖分的中间点K
int get_weight(const int a, const int b, const int c)
{return weight[a][b] + weight[b][c] + weight[c][a];
}
int main()
{minest_weight_val();printf("result:%d\n",t[1][N-1]);back_track(1,5);return 0;
}void minest_weight_val()
{int i,r,k,j;int min;for (i = 1; i <= N; i++)t[i][i] = 0;for (r = 2; r < N; r++){for (i = 1; i < N-r+1; i++){//计算多边形{Vi-1，Vj}的最小权值j = i +( r -1);min = 9999; //假设最小值for (k = i; k < j; k++){t[i][j] = t[i][k] + t[k+1][j] + get_weight(i-1,k,j);if (t[i][j] < min) //判断是否是最小值{min = t[i][j];s[i][j] = k;}}t[i][j] = min;//取得多边形{Vi-1，Vj}的划分三角最小权值}}
}void back_track(int a, int b)
{if (a == b)return;back_track(a,s[a][b]);back_track(s[a][b]+1,b);//记得这是要加一
printf("最优三角: V%d V%d V%d.\n",a-1,s[a][b],b);
}5.多边形游戏
多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构 成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个 运算符“+”或“*”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。 随后n-1步按以下方式操作：
(1)选择一条边E以及由E连接着的2个顶点V1和V2；
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。 将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新 顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶 点上的整数值。
此时的问题就是对于给定的多边形，计算最高得分
例子
上述图形可以得到的最高分数为33，4*2合并为8，8*5合并为40，40-7合并为33
多边形的顶点和边的顺时针序列表示为： op[1],v[1], op[2],v[2],… ,op[n],v[n]
在所给多边形中，从顶点i(1≤i≤n)开始，长度为j(链中有j 个顶点)的顺时针链p(i，j) 可表示为v[i]，op[i+1]， … ， v[i+j-1]。
如果这条链的最后一次合并运算在op[i+s]处发生(1≤s≤j-1)， 则可在op[i+s]处将链分割为2个子链p(i，s)和p(i+s，j-s)。一个长度为s，另一个长度为j-s。
- 设m1是对子链p(i，s)的任意一种合并方式得到的值，而a 和b分别是在所有可能的合并中得到的最小值和最大值。
- 设m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d 分别是在所有可能的合并中得到的最小值和最大值。依此 定义有a≤m1≤b，c≤m2≤d
- 当op[i+s]='+'时，显然有a+c≤m≤b+d
- 当op[i+s]='*'时，有min{ac，ad，bc，bd}≤m≤max{ac， ad，bc，bd}
上述内容表示主链的最大值可以通过子链的最大值和最小值得到
在构造递归函数的时候，需要同时计算最大值和最小值
设m[i][j][0] 是链p(i,j)合并的最小值，而 m[i][j][[1]是最大值。
若最优合并在 op[i+s] 处将p(i,j)分为2个长 度小于j的子链 p(i,s)和 p(i+s,j-s)，且从 顶点i开始的长度小于j的子链的最大值和最小 值均已计算出。为叙述方便，记
- a=m[i][s][0] b=m[i][s][1],
- c=m[i+s][j-s][0] d=m[i+s][j-s][1]
由于最优断开位置s有1<=s<=j-1的j-1种情况，由此可知
初始边界值，即长度为1的链子，无需断开
m[i][1][0]=v[i],1<=i<=n
m[i][1][1]=v[i], 1<=i<=n
Void Min_Max (int n, int i,int s,int j,int &minf,int &maxf, int m[][][2],char op[])
{//从顶点i开始长度为j顺时针链p(i,j) 表示v[i]，op[i+1]，…，v[i+j-1]int e[4]; //该函数计算minf(i,j,s)和maxf(i,j,s)int r=(i+s-1)%n+1;int a=m[i][s][0],b=m[i][s][1]; //p(i,s) int c=m[r][j-s][0],d=m[r][j-s][1]; //p(i+s,j-s)if (op[r]= =‘+’){minf=a+c;maxf=b+d;}else{e[1]=a*c, e[2]=a*d, e[3]=b*c, e[4]=b*d;minf=maxf=e[1];for (int r=2;r<5;r++){if (minf>e[r]) minf=e[r];if (maxf<e[r]) maxf=e[r];}}
}// int r=(i+s-1)%n+1; 具体解释这句话，由于为环形链，所以需要对n取余
//又由于点是从1开始的，故为了避免出现0，所以需要-1取余后加一//上述代码计算了拆分后两边的选取，下面计算m数组//对每个顶点i，依链长递增顺序计算链长为j的最大值及最小值
Int Poly_Max(int n)
{int minf,maxf;for(int j=2;j<=n;j++)for(int i=1;i<=n;i++)for(int s=1;s<j;s++){Min_Max(n,i,s,j,minf,maxf,m,op);if (m[i][j][0]>minf) m[i][j][0]=minf;if (m[i][j][1]<maxf) m[i][j][1]=maxf;}int temp=m[1][n][1];for (int i=1;i<=n;i++)if (temp<m[i][n][1])temp=m[i][n][1];return temp;//找出最大值
}6.电路布线问题
在一块电路板的上、下2端分别有n个接线柱。根据电路设计， 要求用导线(i,π(i))将上端接线柱与下端接线柱相连，如图所示。 其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上 的第i条连线。对于任何1≤i<j≤n,第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。
电路布线问题要求确定导线集 Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
上图为图例。上面的i连接下面的Π（i）
当i = 1时
当i > 1时
解释一下：如果
不成立的话，那么依据
对于任何1≤i<j≤n,第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。
则这两条线相交，不符合最大不相交子集
对于
,我们可以很轻易的得出，MNS(i,j) = MNS(i-1,j)
根据上述关系写出递推公式
代码如下
#include "stdafx.h"
#include <iostream>
using namespace std;
const int N = 10;
void MNS(int C[],int n,int **size)//C代表上面的Π
{for(int j=0;j<C[1];j++)size[1][j]=0;for(int j=C[1]; j<=n; j++)size[1][j]=1;//这里初始化，当j<C[1]时，无法连线，大于C[1]时，连接一条线for(int i=2; i<n; i++){for(int j=0; j<C[i]; j++)size[i][j]=size[i-1][j]; //当j<c[i]的情形for(int j=C[i]; j<=n; j++){//当j>=c[i]时，考虑(i，c[i])是否属于MNS(i,j)的两种情况size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1);}}//上述为递推公式的实现size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);
} 为了实现相互连接的线的打印
void Traceback(int C[],int **size,int n,int Net[],int& m)
{int j=n;m=0;for(int i=n;i>1;i--){if (size[i][j]!=size[i-1][j]) //此时,(i,c[i])是最大不相交子集的一条边{Net[m++]=i;j=C[i]-1;//更新扩展连线柱区间}}if (j>=C[1]) //处理i=1的情形{Net[m++]=1;}
} 主函数如下
int main()
{int c[] = {0,8,7,4,2,5,1,9,3,10,6};//下标从1开始int **size = new int *[N+1];int k;for(int i=0; i<=N; i++){size[i] = new int[N+1];}MNS(c,N,size);cout<<"电路布线最大不相交连线数目为："<<size[N][N]<<endl;int Net[N],m;Traceback(c,size,N,Net,m);cout<<"最大不相交连线分别为："<<endl;for(int i=m-1; i>=0; i--){k=Net[i];cout<<"("<<k<<","<<c[k]<<") ";}cout<<endl;return 0;
}note：算法MNS的时间复杂度为O(n^2)
7.流水调度问题
n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完 成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上 加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从 第一个作业在机器M1上开始加工，到最后一个作业在机器M2上 加工完成所需的时间最少。
设全部作业的集合为N={1，2，…，n}。SN是N的作业子集。 在一般情况下，机器M1开始加工S中作业时，机器M2还在加工 其它作业，要等时间t后才可利用。将这种情况下完成S中作 业所需的最短时间记为T(S,t)。流水作业调度问题的最优值 为T(N,0)。
当等待时间为t的时候，两台机器共同工作，如果机器M2先完成，那么就会进入等待，如果M1先完成，那么就会堆积作业，使得整体处理时间增加
Johnson不等式
调度满足Johnson法则当且仅当对于任意i < j
所有满足Johnson 法则的调度均为最优调度
流水作业调度问题中的Johnson算法
- 令N1为在M1上处理时间小于M2处理时间，N2则 相反
- 将N1作业按照ai非减序排序，N2按照bi非增序排序
- N1中作业接N2中作业构成最优调度（N1中作业执行完再去执行N2）
其原理在于先执行a时间少的，为M2机器堆叠任务，然后为了避免M1完成M2未完成的情况出现，后面安排M1时间长，M2时间短的，尽量让两台机器并行工作，减少等待时间
作业调度程序
int FlowShop(int n, int a, int b, int c)
{
class Jobtype{public:int operator <= (Jobtype a) const{return (key <= a.key);}int key;int index;bool job;};Jobtype *d=new Jobtype [n];for (int i = 0; i< n; i++) {d[i].key = a[i] > b[i] ? b[i] : a[i];d[i].job = a[i] <= b[i];d[i].index = i;}sort(d, n) //非减排序int j = 0, k = n-1;for (int i = 0; i < n; i++) {//生成N1及N2，由c记录其索引（作业序号）if ( d[i].job ) c[j++] = d[i].index;else c[k--] = d[i].index;
}//计算完成所有作业的时间j = a[c[0]];k = j + b[c[0]];for (int i = 1; i < n;i++) {j + =a[c[i]];k = j < k ? k +b[c[i]] : j + b[c[i]];}delete d;return k;简单办法：
将所有ai和bi分类为非降序列，接下来按照如下规则进行考察
- 如果序列下一个数为aj且作业j还没调度，那么在还没使用的最左位置调度作业j
- 如果下一个数为bj且作业j还没调度，那么在还没使用的最右位置调度作业j
- 如果已经调度了作业j，那么就转到该序列的下一个数
排序的结果为
如该图所示，首先拿出a4，即调度J4，然后拿出b3，即将J3最后一个操作，然后依次进行操作，结果如下（4.0.2.1.3）
8.0-1背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi， 背包的容量为C。问:应如何选择装入背包的物品，使得装 入背包中物品的总价值最大?
问题建模如下
0-1背包子问题如下
设该子问题的最优解为m(i,j)（即代表最大价值）,背包容量为j，可选择物品为i到n，建立递归式子如下
代码如下
template< class Type >
void Knapsack( Type *v, int *w, int c, int n, Type **m)
//v代表每个物品价值，w代表每个物品质量，n代表物品个数，m代表最大价值，背包容量c
{int jMax = min(w[n]-1, c) //背包剩余容量for (int j = 0; j<=jMax; j++) //背包不同剩余容量j <= jMax < cm[n][j]=0;for(int j=w[n]; j<=c; j++)m[n][j]=v[n];for(int i=n-1; i>1; i--){jMax=min(w[i]-1, c);for(int j=0; j<=jMax; j++) //背包剩余容量j <= jMax<cm[i][j]=m[i+1][j]; //没产生任何效益//for(int j=w[i]; j<=c; j++) //背包剩余容量j>wim[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]); //效益值增长vi}m[1][c]=m[2][c];if (c>=w[1])m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1]);
}Template < class Type >//求最优解xi
void Traceback(Type **m, int w, int c, int n, int x)
{for(int i=1; i<n; i++)if (m[i][c]==m[i+1][c]) x[i]=0;else { x[i]=1;c= c- w[i]; }x[n]=(m[n][c])?1:0;
}说明:当wi为正整数时，用二维数组m[][]来存储m(i,j)相应的最 优值。
原有时间复杂度为
若引入阶梯函数，可以将时间复杂度降低为
9.最优二叉搜索树
若左子树不空，则左子树的所有结点的值小于根节点的值
若右子树不空，则右子树所有结点的值大于根节点的值
左右子树也分别为二叉搜索树
在随机情况下，二叉搜索树的平均查找长度为logn量级的
设 S={x1, x2, ···, xn} 是一个有序集合，且x1, x2, ···, xn表示有序集合的二叉搜索树，利用二叉树的顶点 存储有序集合中的元素
在所有表示有序集S的二叉搜索树中找出一棵具有最小平 均路长的二叉搜索树。
wij代表搜索到i到j的概率
则有递推公式为
最优二叉搜索树Tij的平均路长为pij， Tij的根结点存储元素 为Xk,其左子树和右子树的平均路长分别为Pi,k-1和Pk+1,j
算法optimalBST（）中，用s[i][j]保存最优子树Tij的根结点 中元素，当s[1][n]=k时，xk为所求二叉搜索树根结点元素， 其左子树为T1,k-1，而s[1][k-1]=i表示左子树T1,k-1的根结点 元素为xi，依次类推，可以有s记录的信息在O(n)时间内构造 出所求的最优二叉搜索树。
//打印最优二叉查找树的结构
//打印出[i,j]子树，它是根r的左子树和右子树
void printOptimalBST(int i,int j,int r)
{int rootChild = root[i][j];//子树根节点if (rootChild == root[1][n]){//输出整棵树的根cout << "k" << rootChild << "是根" << endl;printOptimalBST(i,rootChild - 1,rootChild);printOptimalBST(rootChild + 1,j,rootChild);return;}if (j < i-1)return;else if (j == i-1) //遇到虚拟键{if (j < r)cout << "d" << j << "是" << "k" << r << "的左孩子" << endl;elsecout << "d" << j << "是" << "k" << r << "的右孩子" << endl;return;}else//遇到内部结点{if (rootChild < r)cout << "k" << rootChild << "是" << "k" << r << "的左孩子" << endl;elsecout << "k" << rootChild << "是" << "k" << r << "的右孩子" << endl;}printOptimalBST(i, rootChild-1, rootChild);printOptimalBST(rootChild + 1, j, rootChild);}改进
