一直没写过动态规划、主要是因为动态规划博大精深、自己又学得似是而非，并且诸如插头、树状啥的根本就不敢看。所以一直就这么搁浅了、今天突然又看了一下上周做的FOJ月赛，其中有一题就是动态规划，想想这题里又学到了新的算法，固想写个总结供日后复习之用。第一问很简单，裸的LCS，直接敲。第二问有难度（对于我来说），用比较专业一点的术语，第二问是一个“字符串相似度匹配”。其思想就是动态规划：从两个字符串的左边开始比较,记录已经比较过的子串相似度(实际上叫做距离),然后进一步得到下一个字符位置时的相似度。 用下面的例子: GUMBO和GAMBOL。当算到矩阵D[3,3]位置时,也就是当比较到GUM和GAM时,要从已经比较过的3对子串GU-GAM, GUM-GA和GU-GA之中选一个差别最小的来当它的值. 所以要从左上到右下构造矩阵。
编辑距离的伪算法：
整数 Levenshtein距离(字符 str1[1..lenStr1], 字符 str2[1..lenStr2]) 宣告 int d[0..lenStr1, 0..lenStr2] 宣告 int i, j, cost 对于 i 等于 由 0 至 lenStr1 d[i, 0] := i 对于 j 等于 由 0 至 lenStr2 d[0, j] := j 对于 i 等于 由 1 至 lenStr1 对于 j 等于 由 1 至 lenStr2 若 str1[i] = str2[j] 则 cost := 0 否则 cost := 1 d[i, j] := 最小值( d[i-1, j ] + 1, // 删除 d[i , j-1] + 1, // 插入 d[i-1, j-1] + cost // 替换 ) 返回 d[lenStr1, lenStr2]
PS：这人觉得学习动态规划是一个长久的过程、其思维方式的培养需要慢慢一步一步来，不可幻想一口吃成个大胖子。我想DD大牛的背包九讲也能够初学者看上一半个月的吧！
FOJ 2024 代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define init(a,what) memset(a,what,sizeof(a)) #define max(a,b) (a)>(b) ? (a):(b) #define min(a,b) (a)<(b) ? (a):(b) #define min3(a,b,c) min(a,min(b,c)) #define read freopen("zx.in","r",stdin) #define write freopen("zx.out","w",stdout) const int N=1000+10; int ncase,cur,f[N][N],d[N][N]; char buf1[N],buf2[N]; int main() { read, write; scanf("%d",&ncase); for(int ii=1;ii<=ncase;ii++) { scanf("%s%s",buf1,buf2); init(f,0); init(d,0); int temp=0; int len1=strlen(buf1), len2=strlen(buf2); for(int i=0;i<=len1;i++) d[i][0]=i; for(int j=0;j<=len2;j++) d[0][j]=j; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(buf1[i-1]==buf2[j-1]) { temp=0; f[i][j]=f[i-1][j-1]+1; } else { temp=1; f[i][j]=max(f[i-1][j],f[i][j-1]); } d[i][j]=min3(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+temp); } printf("Case %d: LCS=%d EditStep=%d/n",ii,f[len1][len2],d[len1][len2]); } return 0; }
