C++ 解法, 执行用时: 1ms, 内存消耗: 632KB, 提交时间: 2017-08-16

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
//空间可以优化成O(n)
int main() {
    string s1, s2;
    while (cin >> s1 >> s2) {
        vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
        for (int i = 1; i <= s2.length(); i++) dp[0][i] = i;
        for (int i = 1; i <= s1.length(); i++) dp[i][0] = i;
        for(int i=1;i<=s1.length();i++)
            for (int j = 1; j <= s2.length(); j++) {
                int min1 = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                dp[i][j] = min((s1[i - 1] == s2[j - 1] ? 0 : 1) + dp[i - 1][j - 1], min1);
            }
        cout << dp[s1.size()][s2.size()] << endl;
    }
}

C 解法, 执行用时: 2ms, 内存消耗: 300KB, 提交时间: 2021-08-01

#include <stdio.h>
#include <string.h>

int main(void){
    const int sz = 500;
    char rows[sz], cols[sz];
    while(gets(rows) != NULL && gets(cols) != NULL)
    {
        int line[strlen(rows) + 1];
        for(int i = 0; i <= strlen(rows); ++i) 
            line[i] = i;
        for(int i = 1; i <= strlen(cols); ++i)
        {
            int prev = line[0];
            line[0] = i;
            for(int j = 1; j <= strlen(rows); ++j)
            {
                int t = line[j];
                if(rows[j-1] == cols[i-1]) 
                    line[j] = prev;
                else
                {
                    if(line[j] > prev)
                    {
                        line[j] = prev;
                    }
                    if(line[j] > line[j-1])
                    {
                        line[j] = line[j-1];
                    }

                    ++line[j];
                }
                prev = t;
            }
        }
        printf("%d\n", line[strlen(rows)]);
    }
    return 0;
}