思路：这个题放在基础题，分值还是零分，好歹也给人家动态规划一点面子啊！刚开始写的想法是找到其最大公共字串，然后用两个字符串中最长字符串的长度减掉最大公共字符串的长度，这个思路应该也是对的，几天前写的，好像没用动态规划写然后错了；然后百度了下是用动态规划，然后重新写了下。换了个思路，然后手写了下样例的dp数组，寻找状态之间的关系。
以下AC代码：
#include#include using namespace std;const int max = 1010;int dp[max][max];int main(){ string a, b; cin >> a >> b; for (int i = 0; i <= a.length(); i++){ for (int j = 0; j <= b.length(); j++){ if (i == 0){ dp[0][j] = j; } else{ if (j == 0){ dp[i][0] = i; continue; } if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > dp[i][j - 1] + 1)dp[i][j] = dp[i][j - 1] + 1; if (dp[i][j] > dp[i - 1][j] + 1)dp[i][j] = dp[i - 1][j] + 1; } } } cout << dp[a.length()][b.length()] << endl; return 0;}