从零开始学动态规划

动态规划的定义：
动态规划是运筹学的一个分支，是求解决策过程的最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。在各种算法中，我认为动态规划是较难掌握好的，主要难在模型的建立。
解题的一般步骤是：
1.找出最优解的性质，刻画其结构特征和最优子结构特征；
2.递归地定义最优值，刻画原问题解与子问题解间的关系；
3.以自底向上的方式计算出各个子问题、原问题的最优值，并避免子问题的重复计算；
4.根据计算最优值时得到的信息，构造最优解。
话不多说，我们来看几个具体的例子慢慢理解它：
1.矩阵连乘
给定n个可连乘的矩阵{A1, A2, …,An}，根据矩阵乘法结合律，可有多种不同计算次序，每种次序有不同的计算代价，也就是数乘次数。例如给定2个矩阵A[pi,pj]和B[pj,pk]，A×B为[pi,pk]矩阵，数乘次数为pi×pj×pk。将矩阵连乘积Ai…Aj简记为A[i:j] ，这里i≤j。考察计算A[i:j]的最优计算次序，设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则A[i:j]的计算量=A[i:k]的计算量+A[k+1:j]的计算量+A[i:k]和A[k+1:j]相乘的计算量。计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。即矩阵连乘计算次序问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质，问题具有最优子结构性质是该问题可用动态规划算法求解的显著特征。POJ1651就是一道具有类似思想的题目。题目大意是给出N个数，每次从中抽出一个数(第一和最后一个不能抽)，该次的得分即为抽出的数与相邻两个数的乘积。一直这样将每次的得分累加直到只剩下首尾两个数为止，问最小得分。
AC代码：

#define maxn 105
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[maxn][maxn],a[maxn];
int main()
{
int n;
cin>>n;
int i,j,k,len;
memset(dp,0,sizeof(dp));
//len是设置步长,也就是j减i的值
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n-2;i++) dp[i][i+2]=a[i]*a[i+1]*a[i+2];
//如果只有三个数就直接乘起来
for(len=3;len<n;len++)
{
for(i=0;i+len<n;i++)
{
j=i+len;
for(k=i+1;k<j;k++)
{
if(dp[i][j]==0) dp[i][j]=dp[i][k]+dp[k][j]+a[i]*a[k]*a[j];
else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
}
}
}
cout<<dp[0][n-1]<<endl;
}

2.走金字塔
给定一个由n行数字组成的数字三角型，如图所示。设计一个算法，计算从三角形的顶至底的一条路径，使该路径经过的数字总和最大。路径上的每一步都只能往左下或右下走，给出这个最大和。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
这个问题来源于POJ1163。对于这种问题，我们可以有正向和反向两种思考方式。正向思考这个问题，dp[i][j]表示从第一行第一列到第i行第j列最大的数字总和；反向思考这个问题，dp[i][j]表示从第i行第j列到最后一行最大的数字总和。反向思考的代码要简洁一些，在POJ上这两份代码所用时间都是32MS。当然我们还可以对空间再进行优化，这里就不再细说了。
AC代码：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int triangle[110][110],dp[110][110];
int main()
{
int N;
cin>>N;
memset(dp,0,sizeof(dp));
memset(triangle,0,sizeof(triangle));
for(int i=1;i<=N;i++)
{
for(int j=1;j<=i;j++)
{
cin>>triangle[i][j];
}
}
dp[1][1]=triangle[1][1];
for(int i=2;i<=N;i++)
{
for(int j=1;j<=i;j++)
{
if(j!=1) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+triangle[i][j]);
if(j!=i) dp[i][j]=max(dp[i][j],dp[i-1][j]+triangle[i][j]);
}
}
int max=-1;
for(int i=1;i<=N;i++)
{
if(dp[N][i]>max) max=dp[N][i];
}
cout<<max<<endl;
}

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int triangle[110][110],dp[110][110];
int main()
{
int N;
cin>>N;
memset(dp,0,sizeof(dp));
memset(triangle,0,sizeof(triangle));
for(int i=1;i<=N;i++)
{
for(int j=1;j<=i;j++)
{
cin>>triangle[i][j];
}
}
for(int i=1;i<=N;i++)
{
dp[N][i]=triangle[N][i];
}
for(int i=N-1;i>=1;i–)
{
for(int j=1;j<=i;j++)
{
dp[i][j]=max(dp[i+1][j]+triangle[i][j],dp[i+1][j+1]+triangle[i][j]);
}
}
cout<<dp[1][1]<<endl;
}

3.最长公共子序列(LCS)
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij(j是i的下标)。例如对序列X={A，B，C，B，D，A，B}，子序列Z={B，C，D，B} ，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X
和Y的公共子序列。给定2个序列X={x1, x2,…, xm}和Y={y1,y2,…,yn}，需要找出X和Y的最长公共子序列。例如X=(A, B, C, B, D,A, B)，Y=(B, D,C, A,B,A)，最长公共子序列是BCBA，长度为4。POJ1458就是一道LCS的入门题。
考虑最长公共子序列问题如何分解成子问题，设A=a0a1…am-1，B=b0b1…bm-1，并设Z=z0z1…zk-1为它们的最长公共子序列。不难证明有以下性质：
如果am-1=bn-1，则一定有zk-1=am-1=bn-1，且z0z1…zk-2是a0a1…am-2和“b0b1…bn-2的一个最长公共子序列；
如果am-1!=bn-1，则若zk-1!=am-1，蕴涵z0z1…zk-1是a0a1…am-2和b0b1…bn-1的一个最长公共子序列；
如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵z0z1…zk-1是a0a1…am-1和b0b1…bn-2的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则找a0a1…am-2和b0b1…bn-2的最长公共子序列加1即可；如果am-1!=bn-1，则要解决两个子问题，找出a0a1…am-2和b0b1…bn-1的一个最长公共子序列和找出a0a1…am-1和b0b1…bn-2的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i]=Y[j]还是X[i]!=Y[j]，就可以计算出c[i][j]。问题的递归式写成：

recursive formula

AC代码：

#include<cstring>
#include<iostream>
#define MAXV 1000
using namespace std;
int dp[MAXV][MAXV];
char s1[MAXV],s2[MAXV];
bool issame(int a,int b)
{
return a==b?1:0;
}
int max(int a,int b,int c)
{
if(a>=b&&a>=c) return a;
if(b>=a&&b>=c) return b;
return c;
}
int main()
{
int len1,len2,i,j;
while(cin>>s1>>s2)
{
memset(dp,0,sizeof(dp));
len1=strlen(s1);
len2=strlen(s2);
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
dp[i][j]=max(dp[i-1][j-1]+issame(s1[i-1],s2[j-1]),dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[len1][len2]<<endl;
}
}

还有一个例子：回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。比如字符串Ab3bd，在插入两个字符后可以变成一个回文词(dAb3bAd)或(Adb3bdA)。然而，插入两个以下的字符无法使它变成一个回文词。写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。把原串翻转，再求原串和翻转后串的最长公共子序列，即原串中的最长的回文词。用原串长度减去最长公共子序列长度就是最后答案。代码很简单，就不贴了。
4.最长递增子序列(LIS)
最长递增子序列的定义和最长公共子序列的定义差不多，只不过最长递增子序列是针对单个数组的。 POJ2533就是一道LIS的入门题。设b[i]表示以i为结尾的最长递增子序列的长度，则状态转移方程为：b[i]=max{b[j]+1},1<=j<i,a[j]<a[i].
AC代码：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,a[1010],b[1010];
memset(b,0,sizeof(b));
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
b[i]=1;
for(int j=0;j<i;j++)
{
if(a[j]<a[i]) b[i]=max(b[i],b[j]+1);
}
}
int ans=-1;
for(int i=0;i<n;i++)
{
if(ans<b[i]) ans=b[i];
}
cout<<ans<<endl;
}

其实还有更好的方法，这是我从《挑战程序设计竞赛(第2版)》中摘录的图片。

AC代码：

#include<iostream>
#include<algorithm>
#define MAX_N 1010
#define INF 10010
using namespace std;
int main()
{
int i;
int n;
cin>>n;
int a[1010];
for(i=0;i<n;i++)
{
cin>>a[i];
}
int dp[MAX_N];
fill(dp,dp+n,INF);
for(i=0;i<n;i++)
{
*lower_bound(dp,dp+n,a[i])=a[i];
}
cout<<lower_bound(dp,dp+n,INF)-dp<<endl;
}

第一份代码的运行时间为16MS，第二份代码的运行时间为0MS，可以看出显著的差别。
还有一个例子：N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。你的任务是已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。选中队列中的一个学生，以该学生为核心，分别求出其左侧的最长递增子序列和其右侧的最长递减子序列，两者相加减去1就是以该同学为中心的合唱队的人数，所以我们只需要把每个学生都作为中心遍历一遍，就能得出人数最多的合唱队形，再把总人数减去合唱人数就是需要剔除的人数。代码很简单，就不贴了。
5.最大子段和
给定n个整数组成的序列a1,a2,…,an，求该序列子段和的最大值。最大子段和不能是负数，当序列中均为负数时定义最大子段和为0。例如{-2, 11, -4, 13, -5, -2}的最大子段和为20。首先可以想到用分治的方法解决这个问题，如果将给定的序列a[1..n]分成长度相等的两段a[1..n/2]和a[n/2+1:n]，分别求出这两段的最大子段和。则该给定序列的最大子段和有三种情况：
和a[1…n/2]的最大子段和相同；
和a[n/2+1…n]的最大子段和相同；
最大子段和包含两部分。
前两种情形我们可以用递归方法求出，第三种情形可以分别求出两部分的最大子段和值再相加。序列的最大子段和即为这三种情形的最大值。

#include<iostream>
#include<algorithm>
using namespace std;
int maxsub(int a[],int low,int high)
{
if(low==high) return a[low];
int s1,s2,s3,s31,s32,i,j,sum;
int mid=(low+high)/2;
s1=maxsub(a,low,mid);
s2=maxsub(a,mid+1,high);
i=mid;
s31=a[mid];
while((s31+a[i-1]>s31)&&(i>low))
{
s31+=a[i-1];
i–;
}
j=mid+1;
s32=a[mid+1];
while((s32+a[j+1]>s32)&&(j<high))
{
s32+=a[j+1];
j++;
}
sum=s31+s32;
if(sum<s1) sum=s1;
if(sum<s2) sum=s2;
return sum;
}
int main()
{
int a[6]={-2,11,-4,13,-5,-2};
cout<<max(0,maxsub(a,0,5))<<endl;
}

使用动态规划的解法能够获得更好的复杂度。若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且1<=j<=n。注意一点，b[j]一定包括了a[j]。所求的最大子段和为max b[j]，1<=j<=n。由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为:b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。

#include<iostream>
using namespace std;
int maxsub(int a[],int n)
{
int sum=0,b=0;
for(int i=0;i<=n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}
int main()
{
int a[6]={-2,11,-4,13,-5,-2};
cout<<maxsub(a,5)<<endl;
}

POJ2593要求我们求两个不相交子段加起来的最大值。将数组划分成两部分，正向遍历一次逆向遍历一次加起来即可。

AC代码：

#include<cstring>
#include<iostream>
using namespace std;
const int INF=-0xfffffff;
const int maxn=100000;
int n;
int a[maxn+1];
int b[maxn+2];
int m1[maxn+2],m2[maxn+2];
// m1[i]:Max sum of sub array [0,i] of a
// m2[i]:Max sum of sub array [i,n] of a
int maxsum;
int main()
{
while(cin>>n&&n)
{
m1[0]=m2[n+1]=INF;
memset(b,0,sizeof(b));
for(int i=1;i<=n;++i)
{
cin>>a[i];
if(b[i-1]>=0) b[i]=b[i-1]+a[i];
else b[i]=a[i];
m1[i]=b[i]>m1[i-1]?b[i]:m1[i-1];
}
for(int i=n;i>=1;–i)
{
if(b[i+1]>=0) b[i]=b[i+1]+a[i];
else b[i]=a[i];
m2[i]=b[i]>m2[i+1]?b[i]:m2[i+1];
}
maxsum=INF;
for(int i=1;i<n;++i)
{
if(m1[i]+m2[i+1]>maxsum) maxsum=m1[i]+m2[i+1];
}
cout<<maxsum<<endl;
}
}

POJ1050要求我们求给定矩阵的最大子矩阵和。找出所有的连续行，然后计算每列从第i行到第j行的和，之后对这n个列的和进行一维最大子段和的计算，并找出最大的值。当然，找出所有的连续列也是一样的。
AC代码：

#define MAX 101
#include<cstdio>
#include<iostream>
int main()
{
int n;
int a[MAX][MAX]={0};
int colsum[MAX][MAX]={0};
int max=0,sum;
scanf(“%d”,&n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf(“%d”,&a[i][j]);
colsum[i][j+1]=colsum[i][j]+a[i][j];
}
}
for(int i=0;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
sum=0;
for(int k=0;k<n;k++)
//每列的和
{
if(sum>0) sum+=colsum[k][j]-colsum[k][i];
else sum=colsum[k][j]-colsum[k][i];
if(sum>max) max=sum;
}
}
}
printf(“%d\n”,max);
}

6.凸多边形最优三角剖分
用多边形顶点的逆时针序列表示凸多边形，即P={V0,V1,…,Vn}表示具有n+1条边的凸多边形。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。若P={V0,V1……Vn}的最优三角剖分T包含三角形V0VkVn,则T的权为三个部分权之和：三角形V0VkVn的权，多边形{V0,V1……Vk}的权和多边形{Vk,Vk+1……Vn}的权之和。可以断言，由T确定的这两个子多边形的三角剖分也是最优的。设t[i][j]为凸多边形{Vi-1,Vi……Vj}的最优三角剖分所对应的最优权值，则P的最优权值为t[1][n]，有：

#include<iostream>
#define N 6
using namespace std;
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-1VkVj}的最优权值
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];
}
void minweight()
{
int minval;
for(int i=1;i<N;i++) t[i][i]=0;
for(int r=2;r<N;r++)
{
for(int i=1;i<N-r+1;i++)
{
int j=i+r-1;
minval=9999;
for (int 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]<minval)
{
minval=t[i][j];
s[i][j]=k;
}
}
t[i][j]=minval;
//取得多边形Vi-1Vj的最小划分权值
}
}
}
void backtrack(int a, int b)
{
if (a==b) return;
backtrack(a,s[a][b]);
backtrack(s[a][b]+1,b);
cout<<”最优三角:”<<”v”<<a-1<<”v”<<s[a][b]<<”v”<<b<<endl;
}
int main()
{
minweight();
cout<<”result:”<<t[1][N-1]<<endl;
backtrack(1,5);
}

7.背包问题
背包问题可以说是最经典的动态规划问题了。在这里，我们只讲解最基本的三种背包问题。
零一背包问题:有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品，每种物品都只能挑选一件，求所有挑选方案中价值总和的最大值。
完全背包问题:有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品，每种物品都可以挑选多件，求所有挑选方案中价值总和的最大值。
部分背包问题:有n种重量和价值分别为Wi和Vi的物品。从这些物品中挑选出总重量不超过w的物品，第i种物品最多选mi个，求所有挑选方案中价值总和的最大值。
我们用dp[n][w]表示从前n种物品中挑选出总重量不超过w的物品时所用挑选方案价值总和的最大值。初始化时dp[0][i]=dp[i][0]=0。大家可以自己画张表推导一下就明白了。
零一背包：

#include<iostream>
#include<algorithm>
using namespace std;
void solve();
int n,w;
int W[100]={0};
int V[100]={0};
int dp[100][100];
int main()
{
int i,j;
cin>>n>>w;
for(i=0;i<=n;i++) dp[i][0]=0;
for(j=0;j<=w;j++) dp[0][j]=0;
for(i=0;i<n;i++) cin>>W[i]>>V[i];
solve();
}
void solve()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<=w;j++)
{
if(j<W[i]) dp[i+1][j]=dp[i][j];
else dp[i+1][j]=max(dp[i][j],dp[i][j-W[i]]+V[i]);
}
}
cout<<dp[n][w]<<endl;
}

完全背包：

#include<iostream>
#include<algorithm>
using namespace std;
void solve();
int n,w;
int W[100]={0};
int V[100]={0};
int dp[100][100];
int main()
{
int i,j;
cin>>n>>w;
for(i=0;i<=n;i++) dp[i][0]=0;
for(j=0;j<=w;j++) dp[0][j]=0;
for(i=0;i<n;i++) cin>>W[i]>>V[i];
solve();
}
void solve()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<=w;j++)
{
if(j<W[i]) dp[i+1][j]=dp[i][j];
else dp[i+1][j]=max(dp[i][j],dp[i+1][j-W[i]]+V[i]);
}
}
cout<<dp[n][w]<<endl;
}

零一背包和完全背包的代码差别不大。对于部分背包问题，我们可以把它转化成零一背包问题。把mi分解为mi=1+2+4+…+2^k+a的形式，把mi个重量和价值分别为wi和vi的物品看成重量和价值分别为wix,vix的k+2个物品。例如，假如某种物品有14件，那么我们可以将它分解为价值和代价分别为1price+1cost，2price+2cost，4price+4cost，7price+7cost的4种物品，这样我们总可以将1-13之内的数用这几个数来表示，遍历完所有的状态。

#include<iostream>
#define MAX_N 1000
#define MAX_W 1000
using namespace std;
int N,W;
int w[MAX_N],v[MAX_N],m[MAX_N];
int dp[MAX_W+1];
int main()
{
cin>>N>>W;
for(int i=0;i<N;i++) cin>>w[i]>>v[i]>>m[i];
for(int i=0;i<N;i++)
{
int num=m[i];
for(int k=1;num>0;k<<=1)
{
int mul=min(k,num);
for(int j=W;j>=w[i]*mul;j–) dp[j]=max(dp[j],dp[j-w[i]*mul]+v[i]*mul);
num-=mul;
}
}
cout<<dp[W]<<endl;
}

8.最优二叉搜索树
在《算法导论》中对于这个问题有详细的描述。如果在二叉树中查找元素不考虑概率及查找不成功的情况下，可以采用红黑树或者平衡二叉树来搜索。而现实生活中，查找的关键字是有一定的概率的，就是说有的关键字可能经常被搜索，而有的很少被搜索，而且搜索的关键字可能不存在，为此需要根据关键字出现的概率构建一个二叉树。比如输入法中针对用户习惯可以自动调整词频以减少用户翻查次数，使得经常用的词汇被放置在前面，这样就能有效地加快查找速度。给定一个由n个互异的关键字组成的有序序列K={k1<k2<k3<,……,<kn}和它们被查询的概率P={p1,p2,p3,……,pn}，构造一棵二叉查找树使得查询所有元素的总的代价最小。对于一个搜索树，当搜索的元素在树内时，表示搜索成功。当不在树内时，表示搜索失败，用一个虚叶子节点来标示搜索失败的情况，因此需要n+1个虚叶子节点{d0<d1<……<dn}，对于应di的概率序列是Q={q0,q1,……,qn}。其中d0表示搜索元素小于k1，dn表示搜索元素大于kn。di(0<i<n)表示搜索节点在ki和k(i+1)之间。因此有公式：

由每个关键字和每个虚拟键被搜索的概率，可以确定在一棵给定的二叉查找树内一次搜索的期望代价。设一次搜索的实际代价为检查的节点个数，即所发现的节点的深度加上1。所以一次搜索的期望代价为：

需要注意的是一棵最优二叉查找树不一定是一棵整体高度最小的树，也不一定总是把最大概率的关键字放在根部。对于这一点可以很容易找到反例。定义e[i,j]为搜索一棵包含关键字ki，……，kj的最优二叉查找树的期望代价，当j=i-1时，说明此时只有虚拟键di-1，故e[i,i-1] = qi-1；当j≥i时，需要从ki，……，kj中选择一个根kr，然后用关键字ki，……，kr-1来构造一棵最优二叉查找树作为左子树，用关键字kr+1，……，kj来构造一棵最优二叉查找树作为右子树。定义一棵有关键字ki，……，kj的子树概率的总和为：

当一棵树成为一个节点的子树时子树中每个节点深度都增加1，期望搜索代价增加量为子树中所有节点概率的总和。因此如果kr是一棵包含关键字ki，……，kj的最优子树的根，则有：

用root[i,j]来记录关键字ki，……，kj的子树的根，另外为了防止重复计算，用二维数组来保存w(i,j)的值，其中w[i,j] = w[i,j-1]+pj+qj。

#include<iostream>
#define N 5
#define MAX 999999.99999
using namespace std;
void optimal_binary_search_tree(float *p,float *q,int n,float e[N+2][N+1],int root[N+1][N+1]);
void Construct_Optimal_BST(int root[N+1][N+1],int i,int j,bool flag);
int main()
{
float p[N+1]={0,0.15,0.10,0.05,0.10,0.20};
float q[N+1]={0.05,0.10,0.05,0.05,0.05,0.10};
float e[N+2][N+1];
int root[N+1][N+1];
int i,j;
optimal_binary_search_tree(p,q,N,e,root);
cout<<”最优二叉查找树的代价为: “<<e[1][N]<<endl;
cout<<”最优二叉查找树的结构描述如下：”<<endl;
Construct_Optimal_BST(root,1,N,0);
}
void optimal_binary_search_tree(float *p,float *q,int n,float e[N+2][N+1],int root[N+1][N+1])
{
int i,j,k,r;
float t;
float w[N+2][N+1];
for(i=1;i<=N+1;++i)
{
e[i][i-1]=q[i-1];
w[i][i-1]=q[i-1];
}
for(k=1;k<=n;++k)
//自底向上寻找最优子树
{
for(i=1;i<=n-k+1;i++)
{
j=i+k-1;
e[i][j]=MAX;
w[i][j]=w[i][j-1]+p[j]+q[j];
for(r=i;r<=j;r++)
{
t=e[i][r-1]+e[r+1][j]+w[i][j];
if(t<e[i][j])
{
e[i][j]=t;
root[i][j]=r;
}
}
}
}
}
void Construct_Optimal_BST(int root[N+1][N+1],int i,int j,bool flag)
{
if(flag==0)
{
cout<<”k”<<root[i][j]<<” is root”<<endl;
flag=1;
}
int r=root[i][j];
//如果左子树是叶子
if(r-1<i)
{
cout<<”d”<<r-1<<” is the left child of “<<”K”<<r<<endl;
}
//如果左子树不是叶子
else
{
cout<<”k”<<root[i][r-1]<<” is the left child of “<<”K”<<r<<endl;
Construct_Optimal_BST(root,i,r-1,1);
}
//如果右子树是叶子
if(r+1>j)
{
cout<<”d”<<j<<” is the right child of “<<”K”<<r<<endl;
}
//如果右子树不是叶子
else
{
cout<<”k”<<root[r+1][j]<<” is the right child of “<<”K”<<r<<endl;
Construct_Optimal_BST(root,r+1,j,1);
}
}

9.双调欧几里得旅行商问题
这个问题是《算法导论》中的思考题。给定平面上n个点，确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的。J.L. Bentley建议通过只考虑双调旅程来简化问题。这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。在这种情况下，存在确定的最优双调路线的O(n*n)时间的算法。

例如，a图是最短闭合路线，但是它不是双调的。b图是最短的闭合双调路线。
首先将各点按照x坐标从小到大排列，定义从Pi到Pj的路径为从Pi开始，从右到左一直到P1，然后从左到右一直到Pj。在这个路径上，会经过P1到Pmax(i,j)之间的所有点且每个点只经过一次。定义d(i,j)为满足这一条件的最短路径，我们只考虑i>=j的情况。同时定义dist(i,j)为点Pi到Pj之间的直线距离。根据题意我们需要求的是d(n,n)。
关于子问题d(i,j)的求解，分三种情况：
当j<i-1时，由定义可知，点Pi-1一定在路径Pi-Pj上，又由于j<i-1,因此Pi的左边的相邻点一定是Pi-1，故d(i,j)=d(i-1,j)+dist(i-1,i)。
当j=i-1时，与Pi相邻的那个点可能是P1到Pi-1中的任何一个，故d(i,i-1)=min{d(k,i-1)+dist(i,k)}，1<=k<i-1。
当j=i时，同理，d(i,i)=min{d(k,i)+dist(i,k)}，1<=k<i。
POJ2677是这个问题的一道模板题。
AC代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n;
double dis[550][550],dp[505][505];
struct Node
{
int x,y;
}node[1500];
bool cmp(Node a,Node b)
{
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
void get_dis()
{
int x1,x2,y1,y2;
for(int i=1;i<=n;++i)
{
x1=node[i].x;
y1=node[i].y;
for(int j=i;j<=n;++j)
{
x2=node[j].x;
y2=node[j].y;
dis[j][i]=dis[i][j]=sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
}
}
}
int main()
{
int x,y;
while(scanf(“%d”,&n)!=EOF)
{
memset(dis,0,sizeof(dis));
for(int i=1;i<=n;++i)
{
scanf(“%d%d”,&x,&y);
node[i]=(Node){x,y};
}
sort(node+1,node+n+1,cmp);
get_dis();
dp[2][1]=dp[1][2]=dis[1][2];
dp[2][2]=2*dis[1][2];
for(int i=3;i<=n;++i)
{
for(int j=1;j<i-1;++j)
{
dp[j][i]=dp[i][j]=dp[i-1][j]+dis[i][i-1];
}
dp[i][i-1]=dp[i-1][i]=dp[i][i]=INF;
for(int k=1;k<i-1;++k)
{
if(dp[i][i-1]-(dp[k][i-1]+dis[k][i])>1e-3)
{
dp[i-1][i]=dp[i][i-1]=dp[k][i-1]+dis[k][i];
}
}
for(int k=1;k<i;++k)
{
if(dp[i][i]-(dp[k][i]+dis[k][i])>1e-3)
{
dp[i][i]=dp[k][i]+dis[k][i];
}
}
}
printf(“%.2f\n”,dp[n][n]);
}
return 0;
}

关于动态规划的基础知识就简要介绍到这里，希望能作为大家继续深入学习的基础。

本文链接地址: 从零开始学动态规划http://www.hongyanliren.com/2018m09/39260.html

红颜丽人

追求技术就像追求#$！不抛弃，不放弃！

从零开始学动态规划

从零开始学动态规划

完全背包：

从零开始学动态规划

完全背包：

相关文章