题目链接：戳一戳

 

思路：

动态规划还是练习的太少，做题根本没思路。

看了别人的题解

我们用dp[ i ][ j ]来代表串s中前i个字符与串t中前j个字符的最小编辑距离

那么只有三种情况

1、 如果串 s 的 前 i-1 和 串t 的 前 j-1 都匹配好了的话  只看第i个和第j个相等不相等就好了

2、如果 串s 的 前 i-1 和 串t 的 前 j 都匹配好了的话  多一个s的第 i 个   +1就好了

3、如果 串s 的 前 i 和 串t 的 前j-1 都匹配好了的话  多一个t的第j个 +1就好了

所以

状态转移方程就是

dp[ i ][ j ] = min( dp[ i-1 ][ j-1 ] + (s[ i ] == t[ j ] ? 0 : 1 )，dp[ i-1 ][ j ] + 1 ,dp[ i ][ j-1 ] + 1 )

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1007;
const int INF=0x3f3f3f3f;
int dp[maxn][maxn];
char s[maxn],t[maxn];
int main(){
    scanf("%s",s+1);
    int l1=strlen(s+1);
    scanf("%s",t+1);
    int l2=strlen(t+1);
    memset(dp,INF,sizeof(dp));
    dp[0][0]=0;dp[0][1]=1;dp[1][0]=1;
    for(int i=1;i<=l1;i++){
        dp[0][i]=i;//第一行
    }
    for(int i=1;i<=l2;i++){
        dp[i][0]=i;//第一列
    }
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            dp[i][j]=min(dp[i-1][j-1]+(s[i]==t[j]?0:1),min(dp[i-1][j]+1,dp[i][j-1]+1));
        }
    }
    printf("%d",dp[l1][l2]);
    return 0;
}