概述
同分治法一样动态规划是通过组合子问题的解而解决整个问题的
动态规划的4个步骤：
1.描述最优解结构；
2.递归定义最优解的值；
3.按自底向上方式计算最优解；
4.由计算出的结果构造最优解；（1-3步是基础，第4步可以略去）
动态规划特点，包含重复子问题，可以用图结构保存中间结果，不用重复计算。
1.装配线调度
（PS：这图太磕碜了，没办法，原来网页版的算法导论在PKU的服务器上有，现在不让访问了，悲剧啊，NB学校就是NB，我等P民只能仰望啊~闲扯啊，各位看官将就着看吧~）
问题：每个车间生产需要生产时间，从不同的生产线调配到另一个生产线需要调配时间，计算最小时间？
1.描述最优解结构（划分子问题，子结构）：按生产线长度划分；
2.递归定义最优解的值：递归求解每个长度的最优解；
3.按自底向上方式计算最优解，按长度从短到长求解；
输入：生产线长度，每个车间的生产时间，每个车间之间的调度时间，
输出：最短长度；
example：
Input：
6
7 9 3 4 8 4
8 5 6 4 5 7
2 3 1 3 4
2 1 2 2 1
output
38
#include <iostream>
using namespace std;
int minT[2][100];
int a[2][100], t[2][100];
int e[2]={2,4}, x[2]={3,2};
int cal( int k, int num)
{
if (num==1)
{
minT[k][1] = e[k]+a[k][1];
return minT[k][1];
}
if(minT[k][num]>0) return minT[k][num];
else
{
minT[k][num] = min(cal(k, num-1), cal((k+1)%2, num-1)+t[(k+1)%2][num-1] )+a[k][num];
return minT[k][num];
}
}
int main()
{
memset(minT, 0, sizeof(minT));
int count;
cin>>count;
cout<<"a & t: "<<endl;
for(int i=1 ;i<=count; i++) cin>>a[0][i];
for(int i=1 ;i<=count; i++) cin>>a[1][i];
for(int i=1 ;i<=count-1; i++) cin>>t[0][i];
for(int i=1 ;i<=count-1; i++) cin>>t[1][i];
int minCost = min(cal(0,count)+x[0] ,cal(1,count)+x[1]);
cout<<"MIN:"<<minCost<<endl;
}
2.矩阵链乘法
n个矩阵连乘，A1,A2,A3,... An; 相乘的顺序不同，
A1,A2,A3,A4会产生5种不同的组合：
1.(A1 (A2 (A3*A4) ) ) 2. (A1 ( (A2*A3) A4) ) 3. ( (A1*A2)(A3*A4) ) 4.( ( (A1(A2*A3) )A4 ) 5.(((A1*A2) A3) A4)
根据不同的组合，计算相乘的次数也不同
要求输出最小相乘次数
输入
矩阵数；（一个值 n）
矩阵的横纵坐标：（n+1个值 ）因为后矩阵的行数等于前坐标的列数
要求计算区间：
输出：
区间的最小计算次数
for example:
输入：
6
30 35 15 5 10 20 25
1 6
输出：
15125
1.描述最优解结构（划分子问题，子结构）：按组合划分；
2.递归定义最优解的值：递归求解每组合的最优解；（并保存在矩阵的相应位置中）
3.按自底向上方式计算最优解，按区间从短到长求解；(可以不断调用矩阵，如果矩阵中有的话)
动态规划方程
s[i,j]=0 (if i=j);
s[i,j]=s[i,k]+s[k+1,j]+p[i-1]p[k]p[j];
#include <iostream>
using namespace std;
#define INF 1000000000;
double s[100][100];
int p[101];
double minMul(int low, int high)
{
if(low==high) return 0;
if(s[low][high]>0) return s[low][high];
double minTmp = INF;
double tmp;
for (int k=low; k<high; k++)
{
tmp=minMul(low,k)+minMul(k+1,high)+p[low-1]*p[k]*p[high];
if(tmp<minTmp)
minTmp = tmp;
}
s[low][high]=minTmp;
return minTmp;
}
int main()
{
memset(s,0,sizeof(s));
int n;
cin>>n;
for(int i=0; i<=n; i++) cin>>p[i];
int left,right;
cin>>left>>right;
double minM = minMul(left,right);
cout<<minM<<endl;
}
3.最长公共子序列
给出两个序列，要求给出这两个序列中的最长公共子序列长度；可以不连续，但必须按顺序
a="ABCBDAB", b="BDCABA" 的最长公共子序列长度为4，为"BCBA"
典型的使用矩阵保存中间值，向上不断求解最优解(相同类型：求解字符串间最短距离)
动态规划方程：
if(i==0 或 j==0)
当f(a[i]==b[j])时 A[i][j]=1;否则 A[i][j]=0;
else：
当f(a[i]==b[j])时 A[i][j]=A[i-1][j-1]+1; 否则 A[i][j]=max(A[i-1][j], A[i][j-1]);
#include <iostream>
#include <string>
using namespace std;
string a="ABCBDAB", b="BDCABA";
int A[100][100];
int main()
{
int la = a.length();
int lb = b.length();
for(int i=0; i<la; i++)
{
for(int j=0; j<lb; j++)
{
if(i==0 || j==0)
{
if(a[i]==b[j]) A[i][j]=1;
else A[i][j]=0;
}
else
{
if(a[i]!=b[j]) A[i][j] = max(A[i-1][j], A[i][j-1]);
else A[i][j]=A[i-1][j-1]+1;
}
}
}
cout<<A[la-1][lb-1]<<endl;
}
4.构造最优二叉查找树
每个节点具有一个期望p，每个叶子节点具有一个期望q，要构造一棵二叉树使得总体查找期望最小。
每个节点具有一个期望p，每个叶子节点具有一个期望q，要构造一棵二叉树使得总体查找期望最小。
Input
6
0.15 0.1 0.05 0.1 0.2
0.05 0.1 0.05 0.05 0.05 0.1
动态规划方程：
概率和：
W(i,j)=q(j) (if i>j 叶子节点)
W(i,j)=W(i,r-1)+p(r)+W(r+1,j)
查找期望：
E(i,j)=W(i,j)(if i>j 叶子节点)
E(i,j)=E(i,r-1)+w(i,j)+E(r+1,j)
#include <iostream>
#define INF 1000000;
using namespace std;
float p[100],q[100];
float w[100][100], e[100][100];
float calW(int i, int j)
{
if(w[i][j]>0) return w[i][j];
if(i > j)
{
w[i][j] = q[j];
return w[i][j];
}
float minw=INF;
for (int r=i; r<=j; r++)
{
w[i][j] = calW(i,r-1)+p[r]+calW(r+1,j);
if(w[i][j]<minw) minw = w[i][j];
}
w[i][j] = minw;
return w[i][j];
}
float calE(int i, int j)
{
if(e[i][j]>0) return e[i][j];
if(i>j)
{
e[i][j] = calW(i,j);
return e[i][j];
}
float minE=INF;
for (int r=i; r<=j; r++)
{
e[i][j] = calE(i, r-1)+calW(i, j)+calE(r+1, j);
if(e[i][j]<minE) minE = e[i][j];
}
e[i][j] = minE;
return e[i][j];
}
int main()
{
int n;
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
cin>>n;
for (int i=1; i<n; i++) cin>>p[i]; //non-leaf
for (int j=0; j<n; j++) cin>>q[j]; //leaf
float all15=calE(1,5);
cout<<all15<<endl;
}