递归和动态规划——最小编辑代价

Posted on | In ,

题目：给定两个字符串str1和str2，再给定3个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。
例：
str1=”abc”,str2=”adc”,ic=5,dc=3,rc=2.
将’b’替换成’d’代价是最小的，返回代价2。
str1=”abc”,str2=”adc”,ic=5,dc=3,rc=100.
将’b’删掉，然后插入’d’代价是最小的，返回代价5+3=8。

实现：如果str1的长度为M，str2的长度为N。经典动态规划方法可以达到时间复杂度和额外的空间复杂度O(M*N)；而通过空间压缩，可以将额外的空间复杂度降为O(min{M,N}+1)。
方法一（经典动态规划）：先生成(M+1)*(N+1)的矩阵dp，dp[i][j]的值表示把str1[0,..i-1]编辑成str2[0,..j-1]的最小代价。
注意：这里为什么要加一行和一列空字符串作匹配呢？如果不加，会发现第一行和第一列很难确定它们的值。比如对于第一行str2[j][0]，已经有str1的第一个字符str1[0]了，这个时候到底应该替换、删除、还是增加呢，状态不好确定。

  1. dp[0][0]表示str1空子串编辑成str2空子串的代价，为0.
  2. 第一列dp[0,..M-1][0]，其中dp[i][0]表示将str[0,..i-1]编辑成str2空子串的代价，即将str[0,..i-1]的所有字符删掉，所以dp[i][0]=dc*i。
  3. 第一行dp[0][0,..N-1]，其中dp[0][J]表示将str[0]空子串编辑成str2[0,…j-1]的代价，即将str2[0,.j-1]的所有字符插入到str[0]空子串中，所以dp[0][j]=ic*i。
  4. 非第一行和第一列，dp[i][j]表示将str1[0,..i-1]编辑成str2[0,..j-1]的最小代价，dp[i][j]的情况可能来自下面的四种情况：
    1）str1[0,..i-1] -> str1[0,..i-2]：删除str[i-1]，最小代价dc；
    str1[0,..i-2] -> str2[0,..j-1]：最小代价dp[i-1][j]。
    dp[i-1][j]+dc：这是str1的当前子串str1[0,..i-1]前一个的子串str1[0,..i-2]与str2当前子串str2[j-1]匹配了，因此需要删除str1当前字符str1[i-1]。
    2）str1[0,..i-1] -> str1[0,..j-2]：最小代价dp[i][j-1]；
    str1[0,..j-2] -> str2[0,..j-1]：插入str[i-1]，最小代价ic。
    dp[i][j-1]+ic：这是str1的当前子串str1[0,..i-1]与str2当前子串str2[j-1]的前一个子串str2[0,..j-2]匹配了，因此需要添加str2当前字符str2[j-1]。
    3）str1[i-1]!=str2[j-1]时，
    str1[0,..i-2] -> str1[0,..j-2]：最小代价dp[i-1][j-1]；
    str1[j-1] -> str2[j-1]：替换str[i-1]，最小代价rc。
    dp[i-1][j-1]+rc：这是str1的当前子串str1[0,..i-1]的前一个子串str1[0,…i-2]与str2当前子串str2[j-1]的前一个子串str2[0,..j-2]匹配了，若str[i-1]!=str2[j-1]，则需要将str1[i-1]替换成str2[j-1]。
    4）str1[i-1]==str2[j-1]时，
    str1[0,..i-2] -> str1[0,..j-2]：最小代价dp[i-1][j-1]。
    dp[i-1][j-1]：这是str1的当前子串str1[0,..i-1]的前一个子串str1[0,…i-2]与str2当前子串str2[j-1]的前一个子串str2[0,..j-2]匹配了，若str[i-1]==str2[j-1]，则对str1[i-1]和str2[j-1]不需做任何处理。
  5. 选择最小值的dp[i][j]，dp最右下角就是最终结果。

动态规划进阶：数组滚动更新（空间压缩），额外的空间复杂度为O(min{M,N}+1）
本题的数组滚动更新与经典的求最小路径的算法的滚动更新又有不同。在经典求最小路径的算法中，原矩阵中dp[i][j]的值来源于dp[i-1][j]和dp[i][j-1]，在dp数组从左往右更新时，dp[j]没有使用相当于原来dp[i-1][j]的值，只使用了dp[j-1]，它相当于原来的dp[i][j-1]的值。
而本题中使用了dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]，因此当使用数组滚动更新时，需要用一个变量保存dp[j-1]的值，它相当于原来的dp[i-1][j-1]。
定义dp数组，长度为min{M,N}+1,将较短的字符串作为列对应的字符串。如果长的字符串作为了列对应的字符串，则将插入代价ic和删除代价dc交换。

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 class MinCost {
	/**
	 * 生成(M+1)*(N+1)的动态规划表
	 * @param str1
	 * @param str2
	 * @param ic 插入代价
	 * @param dc 删除代价
	 * @param rc 替换代价
	 * @return
	 */
	public int minCost1(String str1, String str2, int ic, int dc, int rc) {
		if (str1 == null || str2 == null) {
			return 0;
		}
		char[] chas1 = str1.toCharArray();
		char[] chas2 = str2.toCharArray();
		int m = chas1.length + 1;
		int n = chas2.length + 1;
		int[][] dp = new int[m][n];
		//默认dp[0][0] = 0，不需要重新写出
		for (int i = 1; i < m; i++) {
			dp[i][0] = dc * i;
		}
		for (int j = 1; j < n; j++) {
			dp[0][j] = ic * j;
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (chas1[i-1] != chas2[j-1]) {
					dp[i][j] = dp[i-1][j-1] + rc;
				} else { //chas1[i-1] == chas2[j-1]
					dp[i][j] = dp[i-1][j-1];
				}
				dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dc);
				dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + ic);
			}
		}
		return dp[m-1][n-1];
	}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 通过数组滚动更新降低额外空间复杂度，O({M,N}+1)。
 * 与经典求最小路径算法不同的是，需要使用dp[i-1][j]和dp[i-1][j-1]处的值，
 * 因此需要两个变量对这两个值进行保存。
 * 而经典求最小路径算法中只需要dp[i][j-1]处的值
 * @param str1
 * @param str2
 * @param ic
 * @param dc
 * @param rc
 * @return
 */
public int minCost2(String str1, String str2, int ic, int dc, int rc) {
	if (str1 == null || str2 == null) {
		return 0;
	}
	char[] chas1 = str1.toCharArray();
	char[] chas2 = str2.toCharArray();
	char[] longs = chas1.length >= chas2.length ? chas1 : chas2; //长的字符数组
	char[] shorts = chas1.length < chas2.length ? chas1: chas2; //短的字符数组
	//需要将字符串短的那个字符串做为列对应的字符串，而方法中又是将str2作为对应的列字符串，
	//所以如果str1的长度小于str2，则交换ic和dc。
	if (chas1.length < chas2.length) {
		int temp = ic;
		ic = dc;
		dc = temp;
	}
	//dp数组长度相当于dp矩阵的N+1
	int[] dp = new int[shorts.length + 1];
	//初始化dp数组，相当于dp[0][j]执行插入操作的代价
	for (int j = 1; j < shorts.length + 1; j++) {
		dp[j] = ic * j;
	}
	//从第二行开始滚动更新
	//用pre保存dp[0]的值，相当于保存dp[i-1][j-1]的值；
	//用tmp保存上次dp[j]的值，相当于保存dp[i-1][j]的值。
	for (int i = 1; i < longs.length + 1; i++) {
		int pre = dp[0]; //相当于保存左上角的值，初始为dp[0]为0
		dp[0] = dc * i; //相当于dp[i][0]的删除操作
		for (int j = 1; j < shorts.length + 1; j++) {
			int tmp = dp[j]; //相当于保存dp[i-1][j]的值
			if (longs[i-1] != shorts[j-1]) {
				dp[j] = pre + rc;
			} else{ //chas1[i-1] == chas2[j-1]
				dp[j] = pre;
			}
			dp[j] = Math.min(dp[j], tmp + dc);
			dp[j] = Math.min(dp[j], dp[j-1] + ic);
			pre = tmp; //pre变成dp[j]没更新之前的值
		}
	}
	return dp[shorts.length];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
	//Test
	public static void main(String[] args) {
		MinCost mc = new MinCost();
		String str1 = "ab12cd3";
		String str2 = "abcdf";
		int ic = 5;
		int dc = 3; 
		int rc = 2;
		System.out.println("str1和str2的动态规划表为：");
		char[] cha1 = str1.toCharArray();
		char[] cha2 = str2.toCharArray();
		int[][] dp = mc.minCost1(str1, str2, ic, dc, rc);
		for (int[] i : dp) {
			for (int j : i) {
				 System.out.print(j + " ");
			}
			System.out.println();
		}
		//System.out.println("经典动态规划方法编辑字符串的最小代价为：" + mc.minCost1(str1, str2, ic, dc, rc));
		System.out.println("数组滚动更新动态规划方法编辑字符串的最小代价为：" + mc.minCost2(str1, str2, ic, dc, rc));
	}
}

输出：

1
2
3
4
5
6
7
8
9
10
11
str1和str2的动态规划表为：
0 5 10 15 20 25 
3 0 5 10 15 20 
6 3 0 5 10 15 
9 6 3 2 7 12 
12 9 6 5 4 9 
15 12 9 6 7 6 
18 15 12 9 6 9 
21 18 15 12 9 8 
经典动态规划方法编辑字符串的最小代价为：8
数组滚动更新动态规划方法编辑字符串的最小代价为：8