蓝桥杯2019年第十届国赛真题-最优包含(动态规划)

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int dp[1005][1005] = {0};

int main()

{

    string s, t;

    cin >> s >> t;

    int m = s.size();

    int n = t.size();

    for (int i = 1; i <= m; i++) {

        for (int j = 1; j <= n; j++) {

            if (i >= j) {

                if (s[i-1] == t[j-1]) {

                    dp[i][j] = dp[i-1][j-1];

                } else {

                    dp[i][j] = dp[i-1][j-1] + 1;

                    if (i-1 >= j) {

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

                    }

                }

            }

        }

    }

    cout << dp[m][n] << endl;

    return 0;

}