POJ 3356 AGTC（dp） x串变成y串最小代价

题目：http://poj.org/problem?id=3356

题意：
给你x串和y串，让求操作x串变成y串的最小次数
操作：插入、删除、修改一个字符
思路：用dp[i][j]表示x的前i个字符变成y的前j个字符的最小次数
修改 dp[i][j] = dp[i-1][j-1]+1
插入 dp[i][j]=dp[i][j-1]+1
删除 dp[i][j]=dp[i-1][j]+1
代码：

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
const int N = 1005;

int dp[N][N];
string a,b;
int main()
{
    int len1,len2;
    while(cin >> len1 >> a)
    {
        cin >> len2 >> b;
        for(int i = 0;i <= len1;i++)
            dp[i][0] = i;//删除
        for(int i = 0;i <= len2;i++)
            dp[0][i] = i;//插入

        for(int i = 1;i <= len1;i++)
            for(int j = 1;j <= len2;j++)
        {
            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;
            dp[i][j] = min(dp[i][j], min(dp[i][j-1]+1, dp[i-1][j]+1));//插入，删除
        }
        cout << dp[len1][len2] << "\n";
    }
    return 0;
}

类似的题目