51NOD 1183编辑距离（动态规划）

》》点击进入原题测试《《

思路：这个题放在基础题，分值还是零分，好歹也给人家动态规划一点面子啊！刚开始写的想法是找到其最大公共字串，然后用两个字符串中最长字符串的长度减掉最大公共字符串的长度，这个思路应该也是对的，几天前写的，好像没用动态规划写然后错了；然后百度了下是用动态规划，然后重新写了下。换了个思路，然后手写了下样例的dp数组，寻找状态之间的关系。

以下AC代码：

#include<string>

#include<iostream>

using namespace std;

const int max = ;

int dp[max][max];

int main()

{

    string a, b; cin >> a >> b;

    for (int i = ; i <= a.length(); i++){

        for (int j = ; j <= b.length(); j++){

            if (i == ){

                dp[][j] = j;

            }

            else{

                if (j == ){

                    dp[i][] = i;

                    continue;

                }

                if (a[i - ] == b[j - ]) dp[i][j] = dp[i - ][j - ];

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

                if (dp[i][j] > dp[i][j - ] + )dp[i][j] = dp[i][j - ] + ;

                if (dp[i][j] > dp[i - ][j] + )dp[i][j] = dp[i - ][j] + ;

            }

        }

    }

    cout << dp[a.length()][b.length()] << endl;

    return ;

}

巴特西

51NOD 1183编辑距离（动态规划）

最新文章

热门文章