POJ1159解题报告

原题：思路：这个问题其实等价于 求原来字符串 和 反向字符串最小编辑距离。
只是操作只有 删除、插入和copy。
删除： cost = 1
插入： cost = 1
copy： cost = 0

cost[i][j] = min {cost[i-1][j] + 1, cost[i][j-1] + 1}  if oriStr[i] <> revStr[i]
cost[i][j] = min {cost[i-1][j] + 1, cost[i][j-1] + 1, cost[i-1][j-1]}  if oriStr[i] == revStr[i]

上代码：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define MAX 5001

int cost[2][MAX];
int length;
string oriStr;
string revStr;

bool init() {
    if (cin >> length) {
        cin >> oriStr;
        revStr = oriStr;
        reverse(revStr.begin(), revStr.end());

        return true;
    }

    return false;
}

int dp() {
    for (int i=0; i<=length; i++)
        cost[0][i] = i;
    int cur, pre;

    for (int i=1; i<=length; i++) {
        cur = i % 2;
        pre = (i + 1) % 2;
        cost[cur][0] = i;
        for (int j=1; j<=length; j++) {
            int min = cost[cur][j-1] + 1;
            if (cost[pre][j] + 1 < min)
                min = cost[pre][j] + 1;
            if (oriStr[i-1] == revStr[j-1] && cost[pre][j-1] < min)
                min = cost[pre][j-1];
            cost[cur][j] = min;
        }
    }
    return cost[cur][length] / 2;
}

int main() {
    while (init())
        cout << dp() << endl;

    return 0;
}