编辑距离 51Nod

编辑距离

51Nod - 1183

补一道经典dp问题～

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;

char s[maxn], p[maxn];
int dp[maxn][maxn];

int main(){
    scanf("%s %s", s, p);
    int n = strlen(s);
    int m = strlen(p);
    for(int i = 0; i <= n; i++) dp[i][0] = i;
    for(int i = 0; i <= m; i++) dp[0][i] = i;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (s[i-1] != p[j-1]));
        }
    }
    printf("%d
", dp[n][m]);
}