2 条题解
-
1
#include<iostream> #include<string.h> using namespace std; string a; string b; int dp[2002][2002]; int main() { getline(cin,a); getline(cin,b); int s1=a.length(); int s2=b.length(); for(int i=0;i<=s1;i++) { dp[i][0]=i; } for(int i=0;i<=s2;i++) { dp[0][i]=i; } for(int i=1;i<=s1;i++) { for(int j=1;j<=s2;j++) { if(a[i-1]!=b[j-1]) dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1; else dp[i][j]=min(min(dp[i][j-1],dp[i-1][j-1]),dp[i-1][j-1]-1)+1; } } cout<<dp[s1][s2]; }
信息
- ID
- 124
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 151
- 已通过
- 37
- 上传者