51Nod 1183 编辑距离

题目大意：

题解：
设(dp[i][j])为字符串(A)的前(i)个字符变成字符串(B)的前(j)个字符需要的最小操作数。
若字符串(A)的第(i)个字符与字符串(B)的第(j)个字符相等，则问题变成将字符串(A)的前(i-1)个字符变成字符串(B)的前(j-1)个字符；否则，执行替换、插入或删去字符操作，操作数加一。
状态转移方程为：

[dp[i][j] = min{dp[i - 1][j - 1] + (A[i - 1] != B[j - 1]), dp[i - 1][j] + 1, dp[i][j - 1] + 1)} ]

#include <iostream>
#include <string>
using namespace std;

int dp[1010][1010];
string a, b;

int main() {
    cin >> a >> b;
    int lena = a.length(), lenb = b.length();
    if (!lena) {
        cout << lenb;
    } else if (!lenb) {
        cout << lena;
    } else {
        for (int i = 0; i <= lena; ++i) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= lenb; ++j) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= lena; ++i) {
            for (int j = 1; j <= lenb; ++j) {
                dp[i][j] = min(dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]), min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
        cout << dp[lena][lenb];
    }
    return 0;
}