好吧。我还没习惯Live Writer。这部分被覆盖掉了。贴回来。

编辑距离，编程之美3.3节。这个问题类似于最长公共子序列LCS，所以可以使用DP和滚动数组来简化计算。

int editdist(const string& w1, const string& w2) {    size_t len1 = w1.length(), len2 = w2.length();    if (len1++ < len2++) return editdist(w2, w1);    int* dist = new int[len2];    for (size_t j = 0; j < len2; ++j)        dist[j] = j;    for (size_t i = 1; i < len1; ++i) {        int p = dist[0]++;        for (size_t j = 1; j < len2; ++j) {            int np = dist[j];            if (w1[i-1] == w2[j-1]) {                dist[j] = p;            }            else {                dist[j] = min(dist[j], dist[j-1]) + 1;                dist[j] = min(dist[j], p + 1);            }            p = np;        }    }    int r = dist[len2-1];    delete dist;    return r;}int main() {    string w1, w2;    while (cin>>w1>>w2)        cout<