学步园

思路：

又是一道典型DP！

我们将人生划为诡异的阶段
我们把这个世界表为丰富的状态

package DP;

import java.util.Arrays;

/**
 * Edit Distance 
 * 
 * Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character
 */
public class EditDistance {

	static int[][] dist = null;
	
	public static void main(String[] args) {
		String word1 = "sdfsssjdfhsb";
		String word2 = "cvdsfadfgkdfgj";
		
		dist = new int[word1.length()+1][word2.length()+1];
		for(int[] row : dist){
			Arrays.fill(row, -1);
		}
		
		System.out.println(minDistance(word1, word2));
		System.out.println(minDistance2(word1, word2));
	}
	
	public static int min3(int a, int b, int c){
		return Math.min(Math.min(a, b), c);
	}
	
	// DP bottom-up
	public static int minDistance(String word1, String word2) {
		int[][] distance = new int[word1.length()+1][word2.length()+1];
		
		// 边界情况：当其中一个string为空时，只要一直添加或删除就可以
		for(int i=0; i<=word1.length(); i++){
			distance[i][0] = i;
		}
		for(int j=1; j<=word2.length(); j++){
			distance[0][j] = j;
		}
		
		// 递推，[i][j]处可以由左，上，左上3种情况而来
		for(int i=1; i<=word1.length(); i++){
			for(int j=1; j<=word2.length(); j++){
				distance[i][j] = min3(distance[i-1][j]+1,	// 从上演变
											distance[i][j-1]+1,	// 从左演变
											distance[i-1][j-1]+(word1.charAt(i-1)==word2.charAt(j-1) ? 0 : 1));	// 从左上演变，考虑是否需要替换
			}
		}
		return distance[word1.length()][word2.length()];		// 返回右下角
    }

	// 递归，太慢
	public static int minDistance2(String word1, String word2) {
//		return rec(word1, word1.length(), word2, word2.length());
		return rec2(word1, word1.length(), word2, word2.length());
	}
	
	public static int rec(String word1, int len1, String word2, int len2){
		if(len1 == 0){
			return len2;
		}
		if(len2 == 0){
			return len1;
		}
		if(word1.charAt(len1-1) == word2.charAt(len2-1)){
			return rec(word1, len1-1, word2, len2-1);
		}else{
			return min3(rec(word1, len1-1, word2, len2-1) + 1, 
							rec(word1, len1, word2, len2-1) + 1, 
							rec(word1, len1-1, word2, len2) + 1);
		}
	}
	
	// 添加全局数组，保存状态，用空间换时间 DP top-down
	public static int rec2(String word1, int len1, String word2, int len2){
		if(len1 == 0){
			return len2;
		}
		if(len2 == 0){
			return len1;
		}
		
		if(word1.charAt(len1-1) == word2.charAt(len2-1)){
			if(dist[len1-1][len2-1] == -1){
				dist[len1-1][len2-1] = rec2(word1, len1-1, word2, len2-1);
			}
			return dist[len1-1][len2-1];
		}else{
			if(dist[len1-1][len2-1] == -1){
				dist[len1-1][len2-1] = rec2(word1, len1-1, word2, len2-1);
			}
			if(dist[len1][len2-1] == -1){
				dist[len1][len2-1] = rec2(word1, len1, word2, len2-1);
			}
			if(dist[len1-1][len2] == -1){
				dist[len1-1][len2] = rec2(word1, len1-1, word2, len2);
			}
			dist[len1][len2] = min3(dist[len1-1][len2-1]+1, dist[len1][len2-1]+1, dist[len1-1][len2]+1);
			return dist[len1][len2];
		}
	}
}

Ref:

这个视频讲的特别好！

http://www.youtube.com/watch?v=CB425OsE4Fo&list=PL0174E49C0E0DD5C8&index=35

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Java

http://www.cnblogs.com/etcow/archive/2012/08/30/2662985.html

http://blog.csdn.net/alexander_xfl/article/details/11557185

http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/

http://courses.engr.illinois.edu/cs473/lectures.html