文章
68
粉丝
691
获赞
26
访问
577.8k
#define ll long long
#define vec vector<int>
#define inf 0x3f3f3f3f
#define MAX 1005
#define P pair<ll,ll>
#define MOD 1000000
int main() {
string a, b;
int dp[MAX][MAX];
while (cin >> a >> b) {
a = ' ' + a, b = ' ' + b;
int l1 = a.size(), l2 = b.size();
for (int i = 0; i < l1; i++)
dp[i][0] = i;
for (int j = 0; j < l2; j++)
dp[0][j] = j;
for (int i = 1; i < l1; i++)
for (int j = 1; j < l2; j++) {
if (a[i] == b[j])
dp[i][j] = min(1 + dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
else
dp[i][j] = 1 + min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]));
}
cout << dp[l1 - 1][l2 - 1] << endl;
}
}
登录后发布评论
暂无评论,来抢沙发