蓝桥杯2019年第十届国赛真题-最优包含

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int dp[1005][1005];

char s[1005], t[1005];

int n, m;

int main()

{

cin >> s + 1 >> t + 1;

n = strlen(s + 1);

m = strlen(t + 1);

for(int i=1;i<=n;i++)

for (int j = 1; j <=m&&i>=j; j++)

{

dp[i][j] = 1e9;

if (i - 1 >= j)

dp[i][j] = min(dp[i - 1][j], dp[i][j]);

if (s[i] == t[j])

dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);

else

dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);

}

cout << dp[n][m];

return 0;

}