文档介绍：实验二：动态规划
实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和
子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的
一般方法，对较简单的问题 B．动态规划算法
程序如下：
#include<>
#include<>
int lcs_length(char x[], char y[]);
int main()
{
char x[100],y[100];
int len;
while(1)
{
scanf("%s%s",x,y);
if(x[0]=='0') //约定第一个字符串以‘0’开始表示结束
break;len=lcs_length(x,y);
printf("%d\n",len);
}
}
int lcs_length(char x[], char y[] )
{
int m,n,i,j,l[100][100];
m=strlen(x);
n=strlen(y);
for(i=0;i<m+1;i++)
l[i][0]=0;
for(j=0;j<n+1;j++)
l[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(x[i]==y[j-1]) //i,j 从 1 开始，但字符串是从 0 开始
l[i][j]=l[i-1][j]+1;
else if(l[i][j-1]>l[i+1][j])
l[i][j]=l[i][j-1];
else
l[i][j]=l[i-1][j];
return l[m][n];
}
• 例：某公司拟将4 万元，向 A、B、C 三个项目追加投资，三个项目可以有不同的投
资额度，相应的效益值如表所示，问如何分配资金，才使总效益值最大？最优值：
190
A:• 递归方法（自顶向下）+备忘录
#include <iostream>
using namespace std;
int Value[3][5]={47,51,59,71,76,49,52,61,71,78,46,70,76,88,88};
int MaxValue(int Stage, int Money)
{
int splitmoney = 0;
int tempmax=0;int temp = 0