这种一维压缩的方式真的妙啊

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    string str1,str2;
    while(cin>>str1>>str2){
        int m =str1.size();
        int n = str2.size();
        vector<int> dp(n+1,0);

        for(int i =0;i<n+1;i++){
            dp[i]=i;//这里初始化第一行很难理解，我们把dp里的二维给压缩成了一维
            //二维保存了很多信息,但其实我们只需要最后一行的信息。
        }

        int diffi,diffj,diffij;
        for(int i =1;i<m+1;i++){//这里开始第二行了，先把第二行第一列给赋值覆盖掉
            //第一行之前赋的值，准备更新第二行的值了，这个外层就负责更新每一行的第一列
            dp[0]=i;
            diffij = dp[0]-1;//这里其实就是求dp[i][0]的上面一个因为列数为0上面一个dp
            //值肯定要-1这个值后面的内层循环列的时候要更新

            for(int j =1;j<n+1;j++){
                diffj=dp[j];//如果想象成二维的话这里对应着i-1行的j列,就是以前的值我们 
                //我们要保留下来，因为后面列还要靠它来更新.//下面这里一定注意str1[i-1]
                //我这用两种方法每次都搞错这里，i-1才表示前i个字符
                dp[j]=min(dp[j]+1,min(dp[j-1]+1,((str1[i-1]==str2[j-1])?0:1)+diffij));
  //上面这行min里的dp[j-1]之前已经更新过了的，min里的dp[j]其实是i-1行的j列,也就是没有
  //覆盖掉的，等号左边就是即将更新的，他在这个内层循环的下一次又充当min里的dp[j-1]
                diffij = diffj;//这里更新左上角的值，就是内层循环第一句那里为什么要保留了
            }
        }
        cout<<dp[n]<<endl;//最后的dp[n]其实已经遍历m行了，只保留了最后一行
//这种方法空间复杂度就比较低
    }
}

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.next();
            String str2 = sc.next();
            System.out.println(distanceString(str1, str2));
        }
    }
    
    public static int distanceString(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 初始化
        int i = 0, j = 0;
        for (i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        // 动态规划，循环设置值
        for (i = 1; i <= len1; i++) {
            for (j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = minNum(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
    
    public static int minNum(int num1, int num2, int num3) {
        int temp = num1 < num2 ? num1 : num2;
        return temp < num3 ? temp : num3;
    }
    
}

#include<stdio.h>
#define len 500
int getmin(int a, int b, int c) {
    if(a <= b && a <= c) {
        return a;
    } else if (b <= a && b <= c) {
        return b;
    } else if (c <= a && c <= b) {
        return c;
    } else {
        return -1;
    }
}
int getLev(char a[len], char b[len]) {
    int m = strlen(a);
    int n = strlen(b);
    int cost = 0, lev[len][len] = {0};
    for(int i = 0; i <= m; i++) {
        lev[i][0] = i;
    }
    for(int j = 0; j <= n; j++) {
        lev[0][j] = j;
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i-1] == b[j-1]) {
                lev[i][j] = lev[i-1][j-1];
            } else {
                lev[i][j] = getmin(lev[i][j-1] + 1, lev[i-1][j] + 1, lev[i-1][j-1] + 1);
            }
        }
    }
    return lev[m][n];
}
int main() {
    char a[len] = {0};
    char b[len] = {0};
    while(gets(a) && gets(b)) {
        printf("%d\n", getLev(a,b));
    }
}

/*
如何计算编辑距离:
1.两字字串都为空，编辑距离为0
2.当其中一个为空时，编辑距离为另外一个字串的长度。
3.当两个字串非空时（长度分别为i 和 j时），取下面3种情况最小值：
 3.1 当i-1 和 j的编辑距离已知时，直接+1 为 i和j的编辑距离
 3.2 当i 和 j-1的编辑距离已知时，直接+1 为 i和j的编辑距离
 3.3 当i-1 和 j-1的编辑距离已知时，如果i字符和j字符相等则+0，如果不相等则+1为 i和j的编辑距离。
应该用动态规划：
int dp[m+1][n+1] //定义长度为i的字串和长度为j的字串之间的编辑距离
两个字符串最前面插入一个空字符，初始化[i][0] base case 为i，初始化[0][j] base case 为j；
编写状态转移方程。
*/
int cal_distance(string sline1,string sline2)
{
	if ((sline1.empty())&&(sline2.empty())){
		return 0;
	}

	if ((sline1.empty())&&(!sline2.empty())){
		return sline2.size();
	}

	if ((!sline1.empty())&&(sline2.empty())){
		return sline1.size();
	}

	sline1.insert(sline1.begin(),' ');
	sline2.insert(sline2.begin(),' ');

	int m = sline1.size();
	int n = sline2.size();

	vector<vector<int>> dp(m, vector<int>(n,0));//定义长度为i的字串和长度为j的字串之间的编辑距离
	for (int i=0;i<m;i++){
		dp[i][0] = i;
	}
	for (int j=0;j<n;j++){
		dp[0][j] = j;
	}

	for (int i=1;i<m;i++){
		for (int j=1;j<n;j++){
			int add;
			if (sline1[i] == sline2[j]){
				add = 0;
			}
			else{
				add = 1;
			}

			int dp1 = dp[i-1][j-1] + add;
			int dp2 = dp[i-1][j]+1;
			int dp3 = dp[i][j-1]+1;

			if (dp1>dp2){
				dp1 = dp2;
			}
			if (dp1>dp3){
				dp1 = dp3;
			}
			dp[i][j] = dp1;
		}
	}
	return dp[m-1][n-1];
}


int _tmain(int argc, _TCHAR* argv[])
{		
	string sline1, sline2;
	while(cin >> sline1)
	{
		cin >> sline2;

		int length = cal_distance(sline1,sline2);
		cout << length <<endl;
	}
	return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            String s1 = " " + cin.next(), s2 = " " + cin.next();
            System.out.println(calStringDistance(s1, s2));
        }
    }

    public static int calStringDistance(String charA, String charB) {
        int n = charA.length(), m = charB.length();
        int[][] lev = new int[n][m];
        int cost;
        for (int i = 0; i < n; i++) lev[i][0] = i;
        for (int j = 0; j < m; j++) lev[0][j] = j;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                char ch1 = charA.charAt(i), ch2 = charB.charAt(j);
                if (ch1 == ch2) cost = 0;
                else cost = 1;
                lev[i][j] = getMin(lev[i - 1][j] + 1, lev[i][j - 1] + 1, lev[i - 1][j - 1] + cost);
            }
        }
        return lev[n - 1][m - 1];
    }

    public static int getMin(int a, int b, int c) {
        a = Math.min(a, b);
        b = Math.min(b, c);
        return Math.min(a, b);
    }
}

最小编辑距离，经典的动态规划问题之一，类似的还有最大公共子串，最大公共序列，最大递增序列，01
背包问题等等
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        int len1=s1.size();
        int len2=s2.size();
        vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));
        for(int i=1;i<=len1;i++){
            dp[i][0]=i;
        }
        for(int j=1;j<=len2;j++){
            dp[0][j]=j;
        }
        dp[0][0]=0;
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(s1[i-1]==s2[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else{
                    int tem=min(dp[i-1][j],dp[i][j-1]);
                    dp[i][j]=min(dp[i-1][j-1],tem)+1;
                }
            }
        }
        cout<<dp[len1][len2]<<endl;
    }
    return 0;
}

#include<iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
    string a,b;
    while(cin>>a>>b)
    {
        int n = a.size(),m = b.size();
        vector<vector<int>>dp(n+1,vector<int>(m+1));/*dp[x][y]代表将a字符串的前x个字符（从1编号，a的前1个字符为a[0],
                                                      前两个字符为a[0]和a[1]）转换成b字符串的前y个字符*/
        for (int i=0; i<=n; i++) dp[i][0] = i;
        for (int j=0; j<=m; j++) dp[0][j] = j;
        for (int i=1; i<=n; i++) 
            for (int j=1; j<=m; ++j) 
            {
                int d1 = dp[i-1][j] +1,d2 = dp[i][j-1]+1,d3 = dp[i-1][j-1];
                if(a[i-1]!=b[j-1]) d3+=1; //注意由于a的前i-1个字符时从1编号，则第i个字符也是从1编号，为a[i-1]，同理b[j-1]
                dp[i][j] = min(min(d1,d2),d3);
            }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            String s1=input.nextLine();
            String s2=input.nextLine();
            System.out.println(stringDistance(s1.toCharArray(), s2.toCharArray()));
        }
    }
    public static int stringDistance(char[] a, char[] b){
         int[][] len = new int[a.length + 1][b.length + 1];
 
        for (int i = 0; i < len.length; i++) {
            len[i][0] = i;
        }
 
        for (int j = 0; j < len[0].length; j++) {
            len[0][j] = j;
        }
 
        for (int i = 1; i < len.length; i++) {
            for (int j = 1; j < len[0].length; j++) {
                if (a[i - 1] == b[j - 1]) {
                    len[i][j] = len[i - 1][j - 1];
                } else {
                    len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1;
                }
            }
        }
        return len[len.length - 1][len[0].length - 1];
    }
}

import java.util.Scanner;
public class P052StringDistance {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String strA = sc.next();
            String strB = sc.next();
            System.out.println(calStrDis(strA, strB, strA.length(), strB.length()));
        }
        sc.close();
    }
    public static int calStrDis(String strA, String strB, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if(i == 0)//strA为空。
                    dp[i][j] = j;
                else if(j == 0)//strB为空。
                    dp[i][j] = i;
                else if(strA.charAt(i - 1) == strB.charAt(j - 1))//strA和strB最后一个字符相同。
                    dp[i][j] = dp[i-1][j-1];
                else//strA和strB最后一个字符不同。
                    dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]);//strA的所有操作：插入，删除，替换。     }
        }
        return dp[m][n];
        /*//直接递归，运行超时。
        if(m == 0) return n;
        if(n == 0) return m;
        if(strA.charAt(m - 1) == strB.charAt(n - 1))
            return calStrDis(strA, strB, m - 1, n - 1);
        return 1 + min(calStrDis(strA, strB, m, n - 1), calStrDis(strA, strB, m - 1, n), calStrDis(strA, strB, m - 1, n - 1));
        */
    }
    public static int min(int x, int y, int z) {
        if(x < y && x < z)
            return x;
        else if(y < x && y < z){
            return y;
        else
            return z;
    }
                    

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        while(scan.hasNext()){
            String str1 = scan.nextLine();
            String str2 = scan.nextLine();
            
            System.out.println(calStringDistance(str1, str2));
        }
        scan.close();
    }
    
    private static int calStringDistance(String str1, String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        
        int[][] distance = new int[len1+1][len2+1];
        
        for(int i=1; i<=len1; i++){
            distance[i][0]=i;
        }
        for(int j=1; j<=len2; j++){
            distance[0][j]=j;
        }
        int a=0, b=0, c=0;
        for(int i=1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                a = distance[i][j-1]+1;
                b = distance[i-1][j]+1;
                c = str1.charAt(i-1)==str2.charAt(j-1)? distance[i-1][j-1]:distance[i-1][j-1]+1;
                distance[i][j]= Math.min(Math.min(a,b), c);
            }
        }
        return distance[len1][len2];
    }
}

//思路主要：

A[2,…,7]=abcdae和B[2,…,5]=fdfa的距离就可以了。

1．删除A串的第一个字符，然后计算A[2,…,lenA]和B[1,…,lenB]的距离。

2．删除B串的第一个字符，然后计算A[1,…,lenA]和B[2,…,lenB]的距离。

3．修改A串的第一个字符为B串的第一个字符，然后计算A[2,…,lenA]和

B[2,…,lenB]的距离。

4．修改B串的第一个字符为A串的第一个字符，然后计算A[2,…,lenA]和

B[2,…,lenB]的距离。

5．增加B串的第一个字符到A串的第一个字符之前，然后计算

A[1,…,lenA]和B[2,…,lenB]的距离。

6．增加A串的第一个字符到B串的第一个字符之前，然后计算

 * 设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 … ai）
     * 设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 … bj）
     *
     * 设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
     * 当ai==bj时 显然 L(i,j) = L(i-1,j-1)
     * 当ai!=bj时
     *
     *  若将它们修改为相等，则对两个字符串至少还要操作L(i-1,j-1)次
     *  若删除ai或在bj后添加ai，则对两个字符串至少还要操作L(i-1,j)次
     *  若删除bj或在ai后添加bj，则对两个字符串至少还要操作L(i,j-1)次
     *  此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1
     *
     * 显然，L(i,0)=i，L(0,j)=j, 再利用上述的递推公式，可以直接计算出L(i,j)值。

package com.wenjie.huawei;

import java.util.Scanner;

public class CalStringDistance {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String str1 = sc.nextLine();
			String str2 = sc.nextLine();
			System.out.println(stringDistance(str1.toCharArray(),str2.toCharArray()));
		}
	}
    private static int stringDistance(char[] a, char[] b) {
        int[][] len = new int[a.length + 1][b.length + 1];

        for (int i = 0; i < len.length; i++) {
            len[i][0] = i;
        }

        for (int j = 0; j < len[0].length; j++) {
            len[0][j] = j;
        }

        for (int i = 1; i < len.length; i++) {
            for (int j = 1; j < len[0].length; j++) {
                if (a[i - 1] == b[j - 1]) {
                    len[i][j] = len[i - 1][j - 1];
                } else {
                    len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1;
                }
            }
        }
        return len[len.length - 1][len[0].length - 1];
    }
}

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			String strA = in.next();
			String strB = in.next();
			int ic = 1;
			int dc = 1;
			int rc = 1;
			int cost = strEditCost(strA, strB, ic, dc, rc);
			System.out.println(cost);
		}
		in.close();
	}
	public static int strEditCost(String strA, String strB, int ic, int dc, int rc){
		/* 字符串之间的距离，编辑距离，将strA编辑成strB所需的最小代价
		 * 编辑操作包括插入一个字符、删除一个字符、替换一个字符
		 * 分别对应的代价是ic、dc、rc，insert cost、delete cost、replace cost
		 * strA[x-1]代表strA的第x个字符，注意下标是从0开始的,strA[y-1]代表strA的第y个字符
		 * 定义一个代价矩阵为(N+1)*(M+1)，M N 表示strA strB的长度
		 * dp[x][y]表示strA的前x个字符串编辑成 strB的前y个字符所花费的代价
		 * dp[x][y]是下面几种值的最小值：
			 * 1、dp[x][y] = dp[x-1][y] + dc
			 * dp[x-1][y]将strA的前x-1个字符编辑成strB的前y个字符的代价已知，
			 * 那么将将strA的前x个字符编辑成strB的前y个字符的代价dp[x][y]就是dp[x-1][y] + dc
			 * 相当于strA的前x-1个字符编辑成strB的前y个字符，现在变成了strA的前x个字符，增加了一个字符，要加上删除代价
			 * 2、dp[x][y] = dp[x][y-1] + ic
			 * dp[x][y-1]将strA的前x个字符编辑成strB的前y-1个字符的代价已知，
			 * 现在变为strB的前y个字符，相应的在strA前x个操作代价的基础上插入一个字符
			 * 3、dp[x][y] = dp[x-1][y-1]
			 * dp[x-1][y-1]将strA的前x-1个字符编辑成strB的前y-1个字符的代价已知，
			 * strA的第x个字符和strB的第y个字符相同，strA[x-1] == strB[y-1]，没有引入操作
			 * 4、dp[x][y] = dp[x-1][y-1] + rc
			 * strA的第x个字符和strB的第y个字符不相同，strA[x-1] ！= strB[y-1]，
			 * 在strA的前x-1个字符编辑成strB的前y-1个字符的代价已知的情况下，
			 * 计算在strA的前x字符编辑成strB的前y个字符的代价需要加上替换一个字符的代价
		 * */
		int m = strA.length();
		int n = strB.length();
		int[][] dp = new int[m + 1][n + 1];
		for (int i = 1; i <= n; i++) dp[0][i] = i*ic;
		for (int i = 1; i <= m; i++) dp[i][0] = i*dc;
		for (int x = 1; x <= m; x++) {
			for (int y = 1; y <= n; y++) {
				int cost1 = dp[x-1][y] + dc;
				int cost2 = dp[x][y-1] + ic;
				int cost3 = 0;
				if(strA.charAt(x-1) == strB.charAt(y-1))
					cost3 = dp[x-1][y-1];
				else
					cost3 = dp[x-1][y-1] + rc;
				dp[x][y] = Math.min(cost1, cost2);
				dp[x][y] = Math.min(dp[x][y], cost3);
			}
		}
		return dp[m][n];
	}
}

python solution:

def editDistance(str1, str2):
    len1, len2 = len(str1) + 1, len(str2) + 1
    dp = [[0 for i in range(len2)] for j in range(len1)]
    for i in range(len1):
        dp[i][0] = i
    for j in range(len2):
        dp[0][j] = j
    for i in range(1, len1):
        for j in range(1, len2):
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]))
    return dp[-1][-1]


while True:
    try:
        print(editDistance(input(), input()))
    except:
        break