最小编辑代价

给定两个字符串str1和str2，再给定三个整数ic、dc和rc分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。
str1=“abc”，str2=“adc”，ic=5，dc=3，rc=2。
从“abc”编辑成“adc”，把’b’替换成’d’是代价最小的。所以返回2。
str1=“abc”，str2=“adc”，ic=5，dc=3，rc=100。
从“abc”编辑成“abd”，先删除’b’然后插入’d’是代价最小的。所以返回8。
str1=“abc”，str2=“abc”，ic=5，dc=3，rc=2。
不用编辑了，本来就是一样的字符串。所以返回0。

思路

该题目是3个字符串进行比较
dp[i][j]代表str1[0..i-1]编辑成str2[0..j-1]的最小代价
下面具体说明dp矩阵每个位置的值是如何计算的：
1， dp[0][0]=0，表示str1空的子串编辑成str2空的子串的代价为0。
2，矩阵dp第一列即dp[0..M-1][0]。 dp[i][0]表示str1[0..i-1]编辑成空串的最小代价，毫无疑问是把str1[0..i-1]所有字符删掉的代价，所以dp[i][0]=dci。
3，矩阵dp第一行即dp[0][0..N-1]。 dp[0][j]表示空串编辑成str2[0..j-1]最小代价，毫无疑问是在空串里插入str2[0..j-1]所有字符的代价，所以dp[0][j]=ic\j。
4，其他位置按照从左到右再从上到下来计算， dp[i][j]的值只可能来自以下四种情况。
1） str1[0..i-1]可以先编辑成str1[0..i-2]，也就是删除字符str1[i-1]，然后再由str1[0..i-2]编辑成str2[0..j-1]， dp[i-1][j]表示str1[0..i-2]编辑成str2[0..j-1]的最小代价， 那么dp[i][j]可能等于dc+dp[i-1][j]。
2） str1[0..i-1]可以先编辑成str2[0..j-2]，然后str2[0..j-2]再插入字符str2[j-1]编辑成str2[0..j-1]， dp[i][j-1]表示str1[0..i-1]编辑成str2[0..j-2]的最小代价， 那么dp[i][j]可能等于dp[i][j-1]+ic。
3）如果str1[i-1]!=str2[j-1]。先把str1[0..i-1]中str1[0..i-2]的部分可以先变成str2[0..j-2]，然后把字符str1[i-1]替换成str2[j-1]，这样str1[0..i-1]就编辑成str2[0..j-1]了。
dp[i-1][j-1]表示str1[0..i-2]编辑成str2[0..i-2]的最小代价，那么dp[i][j]可能等于dp[i-1][j-1]+rc。
4）如果str1[i-1]==str2[j-1]。先把str1[0..i-1]中str1[0..i-2]的部分可以先变成str2[0..j-2]，因为此时字符str1[i-1]等于str2[j-1]，所以str1[0..i-1]已经编辑成str2[0..j-1]了。
dp[i-1][j-1]表示str1[0..i-2]编辑成str2[0..i-2]的最小代价，那么dp[i][j]可能等于
dp[i-1][j-1]。
5，以上四种可能的值中，选最小值作为dp[i][j]的值。 dp最右下角的值就是最终结果。
具体过程请参看如下代码中的minCost1方法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static int minCost(String str1, String str2, int ic, int dc, int rc) {
	if (str1 == null || str2 == null) {
		return 0;
	}
	char[] chs1 = str1.toCharArray();
	char[] chs2 = str2.toCharArray();
	//多设置一行一列的空值，方便计算
	int row = chs1.length + 1;
	int col = chs2.length + 1;
	
	//dp[0][0]是0，因为空变成空不需要代价
	int[][] dp = new int[row][col];
	for(int i = 1; i < col; i++){
		//把空改为str2的代价是添加
		dp[0][i] = ic*i;
	}
	for(int j = 1; j < row; j++){
		dp[j][0] = dc*j;
	}
	for(int i = 1; i < row; i++){
		for(int j= 1; j < col; j++){
			//在3中取值找最小
			//判断
			if(chs1[i-1] == chs2[j-1]){
				//最后一个相同，不用代价
				dp[i][j] = dp[i-1][j-1];
			}else{
				//不同就修改最后一个
				dp[i][j] = dp[i-1][j-1]+rc;
				}
			//先0,i-1变为0,j-2然后加上j-1
			dp[i][j]=Math.min(dp[i][j], dp[i][j-1]+ic);
			//先0,i-1删除i-1得到0,i-2变为0,j-1
			dp[i][j]=Math.min(dp[i][j], dp[i-1][j]+dc);
		}
	}
	return dp[row-1][col-1];
	
}