递归实现（动态规划,记忆化搜索）

解题思路:

f(i,j)返回d[i][j]，d[i][j]表示S前i个字符中包含T前j个字符至少修改的次数，因此答案将会是f(s_len,t_len)。i==0时修改j次，j==0时修改0次，j>i时修改f(i,j)+j-i次。计算d[i][j]时，若s[i]==t[j]，即当前考虑的两个字符串最后一个字符相等，此时d[i][j]=f(i-1,j-1)，否则，若最后一个字符不相等，d[i][j]=min(f(i-1,j),f(i-1,j-1)+1)。1、f(i-1,j)表示S前i-1个字符中包含T前j个字符至少修改的次数2、f(i-1,j-1)表示S前i-1个字符中包含T前j-1个字符至少修改的次数，加1是因为此时修改S的第i个字符，才能让S前i个字符中包含T前j个字符。最初将d中所有元素初始化为-1，因为修改次数肯定大于等于0，调用f函数时，若d[i][j]>=0，说明它已经算过，不再重复计算，直接返回。

参考代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
char s[1002],t[1002];
int d[1001][1001];
 
int f(int i,int j){
    if(d[i][j]>=0){
        return d[i][j];
    }
     
    if(i==0){
        return d[i][j]=j;
    }
     
    if(j==0){
        return d[i][j]=0;
    }
     
    if(j>i){
        return d[i][j]=f(i,i)+j-i;
    }
     
    if(s[i]==t[j]){
        return d[i][j]=f(i-1,j-1);
    }
    else{
        return d[i][j]=min(f(i-1,j-1)+1,f(i-1,j));
    }
}
 
int main(){
     
    int s_len,t_len,i,j;
     
    scanf("%s",s+1);
    scanf("%s",t+1);
    s_len=strlen(s+1);
    t_len=strlen(t+1);
     
    memset(d,-1,sizeof(d));
     
    printf("%d",f(s_len,t_len));
     
    return 0;
}