POJ3356解题报告

求最小编辑距离。
具体请看

一道典型的DP题目，思路还是蛮简单的。
考虑长度为i和j的子串最优编辑距离，可以分情况讨论一下。
1）经过删除操作得来，那么开销就是cost[i-1][j] + 1，其中cost[i-1][j]表示i-1和j长度的子串之间的最小编辑距离，如果不是最小，我们可以替换成最小的。
2）经过插入操作得到的，那么开销就是cost[i][j-1]+1。
3）直接copy（没有开销）或者替换（开销为1）
    1. 直接copy，要求 x[i] == y[j]，那么开销为cost[i-1][j-1]
    2. 替换，那么开销为cost[i-1][j-1] + 1, 显然替换比直接copy开销大，这个只有当 x[i] != y[j]时候执行。

初始化： cost[i][0] = i, //表示要执行i次删除操作，因为x长度为i，而目标串y长度为0
             cost[0][j] = j, //表示要执行j次插入操作，解释同上。

问题注意：
虽然题目样本里面只有一组测试数据，但是submit时候测试的是多组数据。我提交了好几次只读入一组数据的版本，结果老是WRONG ANSWER，反复检查
解题思路，完全没有问题，真是要命啊。大家要注意一下。

代码写丑了

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

class Solution {
    public:
        Solution(): cost(NULL) {
            source = "";
            target = "";
        }
        ~Solution() {
            if (cost) {
                for (int i=0; i<row; i++)
                    delete []cost[i];
                delete []cost;
            }
        }

        void init(int r) {
            row = r;
            if (row)
                cin >> source;
            cin >> col;
            if (col)
                cin >> target;
            row++;
            col++;

            cost = new int*[row];
            for (int i=0; i<row; i++) {
                cost[i] = new int[col];
                memset(cost[i], 0, sizeof(int)*col);
            }
            for (int i=1; i<row; i++)
                cost[i][0] = i;
            for (int j=1; j<col; j++)
                cost[0][j] = j;
        }

        int minEditionDistance() {
            for (int i=1; i<row; i++) {
                for (int j=1; j<col; j++) {
                    int deletion = cost[i-1][j] + 1;
                    int insertion = cost[i][j-1] + 1;
                    int min = deletion > insertion ? insertion : deletion;
                    if (source[i-1] == target[j-1]) {
                        cost[i][j] = min < cost[i-1][j-1] ? min : cost[i-1][j-1];
                    } else {
                        int change = cost[i-1][j-1] + 1;
                        cost[i][j] = min < change ? min : change;
                    }
                }
            }
            return cost[row-1][col-1];
        }

    private:
        int row;
        int col;
        int **cost;
        string source;
        string target;
};

int main() {
    int row;
    while (cin >> row) {
        Solution solution;
        solution.init(row);
        cout << solution.minEditionDistance() << endl;
    }
    return 0;
}