题解 P2758 【编辑距离】

4396瞎 · 2017-09-26 20:24:25 · 题解

我看题解里的很多都是用递推求解的，只有一位仁兄用的是递归但我觉得他的代码风格跟我还不太一样，而且我也想分享一下自己的解体思路。

做动态规划的题一般分为四个步骤：确定子问题—>定义状态—>转移方程—>避免重复求解

用在这一题当中我的思路如下：

1.确定子问题：

由于对于字符串的操作只有4种情况（删除，添加、更改、不变），所以该题的子问题就是进行了这4种操作后的A字符串变为B字符串需要多少步。

2.定义状态：

也就是说递归的dp函数需要哪些参数，参数越少越好因为需要建memo。后来想到dp（i，j）代表字符串A的前i个字符（包括第i个）变为字符串B的前j个（包括第j个）需要多少步。也就是说解出来dp（lenA，lenB）就可以了。

3.转移方程：

删：dp(i-1，j)+1 //字符串A的前i-1个字符变为字符串B的前j个需要多少步 【把字符串的第i个字符（最后一个）删除了】，删除需要一步因此加1

添：dp(i，j-1)+1 //将B[j]字符加在A字符串的最后面即添加，同样可以理解为将B[j]字符删掉（因为不用再考虑了）。

//字符串A的前i个字符变为字符串B的前j-1个需要多少步 添加需要一步因此加1

替：dp(i-1，j-1)+1 //字符串A和B的最后两个都相等了，因此都不用再考虑

//字符串A的前i-1个字符变为字符串B的前j-1个需要多少步 添加需要一步因此加1

不变：dp（i-1，j-1）//字符串A和B的最后两个都相等，不考虑。感性的说这种情况是理想情况。

4.避免重复求解

这个最简单，建个数组就行。

上代码：

#include<iostream>
#include<cstring>
using namespace std;
string A,B;
char s1[2005],s2[2005];//s1=A , s2=B
int edit[2005][2005];
int dp(int i,int j){ 
    if(edit[i][j]!=-1) return edit[i][j]; 
    if(i==0) return edit[i][j]=j;
    if(j==0) return edit[i][j]=i;
    int bonus=1;
    if(s1[i]==s2[j]) bonus=0;  
    return edit[i][j]=min(min(dp(i-1,j)+1,dp(i,j-1)+1),dp(i-1,j-1)+bonus);
}
int main(){
    cin>>A>>B;
    memset(edit,-1,sizeof(edit));
    int len1=A.length(),len2=B.length();
    for(int i=1;i<=len1;i++ ) s1[i]=A[i-1];//将字符串转成cstring 
    for(int i=1;i<=len2;i++) s2[i]=B[i-1];
    dp(len1,len2);
    cout<<edit[len1][len2];
    return 0;
}