模拟试卷
——第三章动态规划
一、填空题（每小题4分，共20分）
1、动态规划算法的基本要素是（）和（）。

2、（）是动态规划法的变形。

3、（）是最大子段和问题想二维的推广。

4、矩阵连乘问题的算法可由（）设计实现。

5、动态规划算法中，通常不同子问题的个数随问题大小呈（）增长。

二、简答题（每小题6分，共30分）
1、写出设计动态规划算法的主要步骤。

2、简述什么是备忘录方法。

3、简述备忘录法与动态规划法的异同。

4、简述动态规划算法的基本思想。

5. 写出最长公共子序列问题具有的性质。

三、综合题（每小题25分，共50分）
1、用动态规划算法实现最长公共子序列问题。

2、用动态规划算法实现下列问题：设A和B是两个字符串。

我们要用最少的字
符操作将字符串A转换为字符串B，这里所说的字符操作包括：
（1）删除一个字符；
（2）插入一个字符；
（3）将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d（A,B）。

试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d（A,B）。

答案
一、填空题
1、最优子结构、子问题重叠
2、备忘录方法
3、最大子矩阵的问题
4、动态规划法
5、多项式
二、简答题
1、（1）找出最优解的性质，并刻画其结构特征；
（2）递归地定义最优解；
（3）以自底向上的方法计算出最优值；
（4）根据计算最优值时得到的信息，构造最优解。

2、备忘录方法是动态规划算法的变形。

备忘录方法的控制结构与直接递归方法
的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

3、与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下
次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。

与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。

4、动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

5、最长公共子序列问题具有最优子结构性质和子问题重叠性质。

三、综合题
1、解：用动态规划算法求解的算法代码如下：
int lcs_len(char*a,char*b,int c[][N])
{
int m=strlen(a),n=strlen(b),i,j;
for(i=0;i<=m;i++) c[i][0]=0;
for(j=1;j<=n;j++) c[0][j]=0;
for(i=1; i<=m;i++)
for(j=1;j<=n;j++)
if(a[i-1]= =b[j-1]) c[i][j]=c[i-1][j-1]+1;
else if(c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else c[i][j]=c[i][j-1];
return c[m][n];
};
char*build_lcs(char s[],char*a,char*b)
{
int k,i=strlen(a),j=strlen(b),c[N][N];
k=lcs_len(a,b,c);
s[k]=’/0’;
while(k>0){
if(c[i][j]= =c[i-1][j])i--;
else if(c[i][j]= =c[i][j-1])j--;
else{
s[--k]=a[i-1];
i--,j--;
}
}
return s;
}
2、解：用动态规划算法求解的算法代码如下：
int dist()
{
int m=a,size();
int n=b,size();
vector<int>d(n+1,0);
for(int i=1;i<=n;i++) d[i]=i;
for(i=1;i<=m;i++){
int y=i-1;
for(int j=1;j<=n;j++){
int x=y;
y=d[j];
int z=j>1?d[j-1]:i;
int del=a[i-1]= =b[j-1]?0:1;
d[j]=min(x+del,y+1,z+1);
}
}
return d[n];
}。