ZJU/ZOJ 1953 Advanced Fruits 解题报告

题目大意是给出两个字符串，输出包含这两个字符串的最短字符串。

本题模型同样是字符串DP中非常常用的LCS（最长公共字串）模型，用f[i,j]来表示包含第一个字符串前i位和第二个字符串前j位的最短字符串，则可以分两种两种情况考虑，若s1[i]=s2[j]，则f[i,j]=min(f[i-1,j-1],min(f[i-1,j],f[i,j-1]))+s1[i];否则f[i,j]=min(f[i-1,j]+s1[i],f[i,j-1]+s2[j])。

1649561 2008-09-23 16:57:25 Accepted 1953 FPC 0 596 IwfWcf