给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法：
如果想具体看什么时候
是不可行的，因为情况很复杂，你很难去做判断。
所以就用动态规划来解决，考虑在当前情况，三种操作都比较得出最小操作次数即可
dp[i][j]表示word1的前i个字符转为word2的前j个字符的最少操作次数。那么状态转移方程就是
if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]; //分别对应修改(使a[i] == b[j])，增(加在i后面增加一个和b[j]相等)，删除(删除a[i]) else dp[i][j] = min(min(dp[i-1][j-1] + 1,dp[i][j-1] + 1),dp[i-1][j] + 1);
#include<bits/stdc++.h>
using namespace std;
int work(string a,string b)
{
int la = a.length(),lb = b.length();
int dp[la + 1][lb + 1];
dp[0][0] = 0;
for(int i = 1;i <= lb;i++)
dp[0][i] = i;
for(int j = 1;j <= la;j++)
dp[j][0] = j;
for(int i = 1;i <= la;i++)
for(int j = 1;j <= lb;j++)
if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
//分别对应修改(使a[i] == b[j])，增(加在i后面增加一个和b[j]相等)，删除(删除a[i])
else dp[i][j] = min(min(dp[i-1][j-1] + 1,dp[i][j-1] + 1),dp[i-1][j] + 1);
return dp[la][lb];
}
int main()
{
string a,b;
while(cin >> a >> b)
{
cout << work(a,b) << endl;
}
return 0;
}
原文：https://www.cnblogs.com/mch5201314/p/11922215.html