51nod1183编辑距离----DP--字符串最小变化
题目链接:戳一戳
思路:
动态规划还是练习的太少,做题根本没思路。
看了别人的题解
我们用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;
}