算法第三章上机总结

1、选题分析

1.1问题描述

7-4 编辑距离问题 (25 分)

 设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。

1.2算法描述

#include<iostream>

#include<string.h>

using namespace std;

char a[2005], b[2005];

int res [2002][2002];

int temp = 1;

int main (){

cin >> a;

cin >> b;

int la = strlen (a);

int lb = strlen (b);

for(int i = 0; i <= la; i++) res[i][0] = i;

for(int i = 0; i <= lb; i++) res[0][i] = i;

for(int i = 1; i <= la; i++){

for(int j = 1; j <= lb; j++){

if(a[i-1] == b[j-1]) temp = 0; else temp = 1;

int t = min(res[i-1][j] + 1,res[i][j-1] + 1);

res[i][j] = min(t,res[i-1][j-1] + temp);

}

}

cout << res[la][lb];

return 0;

}

1.3问题求解

1.3.1根据最优子结构性质，列出递归方程式。

D[i,j]=min{D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+{0(s[i]=t[j])/1s[i]!=t[j]}

1.3.2给出填表法中的维度、填表范围和填表顺序

维度为m*n,所有都要填，自上而下，自左而右

1.3.3分析该算法的时间和空间复杂度

o（m*n）

2、你对动态规划算法的理解和体会