ShiYu

# 第19节 暴力递归到动态规划（二）

暴力递归改动态规划步骤：

  • 一定要尝试出暴力递归版本，设计暴力递归：重要原则+4种常见尝试模型
    • 从左往右的尝试模型
    • 范围上的尝试模型
    • 多样本位置全对应的尝试模型
    • 寻找业务限制的尝试模型
  • 分析有无重复解
  • 用记忆化搜索实现
    • 分析可变参数范围
    • 写出basecase程式
    • 分析普遍位置依赖
    • 最终推出严格表结构实现动态规划
  • 继续看严格表结构是否可再优化
    • 若是普遍位置求解部分已经是O(1)，不用再优化了
    • 若是普遍位置求解部分是需要遍历的，则尝试使用斜率优化、临近位置观察法优化

设计暴力递归过程的原则：

1）每一个可变参数的类型，一定不要比int类型更加复杂

2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数 例如：贴纸问题

3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可

4）可变参数的个数，能少则少

# 题目一

背包问题

从左往右的尝试模型

给定两个长度都为N的数组weights和values， weights[i]和values[i]分别代表 i号物品的重量和价值。 给定一个正数bag，表示一个载重bag的袋子， 你装的物品不能超过这个重量。 返回你能装下最多的价值是多少?

暴力递归代码：

package class19;

/**
 * 	背包问题
 * @author yangyanchao
 *
 */
public class Test01_Knapsack {
	/**
	 * 	背包问题-暴力递归方法
	 * @param weights
	 * @param values
	 * @param bag
	 * @return
	 */
	public static int maxValue1(int[] weights, int[] values, int bag) {
		if(weights == null || weights.length == 0 || values == null || values.length == 0 
				|| weights.length != values.length || bag < 0 ) {
			// 无效解
			return -1;
		}
		return process(weights, values, 0, bag);
	}

	/**
	 * 	递归过程
	 * @param weights
	 * @param values
	 * @param index   当前来到哪个物品
	 * @param bag     剩余可装载的数量
	 * @return
	 */
	private static int process(int[] weights, int[] values, int index, int bag) {
		if(bag < 0) {
			// 背包容量不够了，那么就是无效的解 一定要放在最前面
			return -1;
		}
		if(index == weights.length) {
			// 装载到最后没有东西可装了，那么最多的价值就是0
			return 0;
		}
		// 要么不装index位置物品
		int p1 = process(weights, values, index + 1, bag);
		int next = process(weights, values, index + 1, bag-weights[index]);
		int p2 = 0;
		if(next != -1) {
			// 要么装index位置物品
			p2 = values[index] + next;
		}
		return Math.max(p1, p2);
	}
	
	public static void main(String[] args) {
		int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
		int[] values = { 5, 6, 3, 19, 12, 4, 2 };
		int bag = 15;
		System.out.println(maxValue1(weights, values, bag));
	}
}
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
54
55
56
57
58
59
60

动态规划代码：

package class19;

/**
 * 	背包问题
 * @author yangyanchao
 *
 */
public class Test01_Knapsack {
	/**
	 * 	背包问题-动态规划方法
	 * @param weights
	 * @param values
	 * @param bag
	 * @return
	 */
	public static int maxValue2(int[] weights, int[] values, int bag) {
		if(weights == null || weights.length == 0 || values == null || values.length == 0 
				|| weights.length != values.length || bag < 0 ) {
			// 无效解
			return -1;
		}
		int N = weights.length;
		int[][] dp = new int[N + 1][bag + 1];
		// 第N行 已经是0了  index == weights.length -> 0
		for(int i = N - 1; i >= 0; i--) {
			for(int j = 0; j <= bag; j++) {
				int p1 = dp[i + 1][j];
				int p2 = 0;
				int next = j - weights[i] < 0 ? -1 : dp[i + 1][j - weights[i]];
				if(next != -1) {
					p2 = values[i] + next;
				}
				dp[i][j] = Math.max(p1, p2);
			}
		}
		return dp[0][bag];
	}
	
	public static void main(String[] args) {
		int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
		int[] values = { 5, 6, 3, 19, 12, 4, 2 };
		int bag = 15;
		System.out.println(maxValue2(weights, values, bag));
	}
}
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

# 题目二

数字串转化为字符串问题

从左往右的尝试模型

规定1和A对应、2和B对应、3和C对应...26和Z对应 那么一个数字字符串比如"111”就可以转化为: "AAA"、"KA"和"AK" 给定一个只有数字字符组成的字符串str，返回有多少种转化结果

暴力递归不优化版本代码：

package class19;

/**
 * -数字串转化为字符串问题
 * -规定1和A对应、2和B对应、3和C对应...26和Z对应
 * -那么一个数字字符串比如"111”就可以转化为:
 * -"AAA"、"KA"和"AK"
 * -给定一个只有数字字符组成的字符串str，返回有多少种转化结果 
 * @author yangyanchao
 *
 */
public class Test02_ConvertToLetterString {
	/**
	 * -暴力递归不优化版本
	 * @param numStr
	 * @return
	 */
	public static int convertToLetterString1(String numStr) {
		if(numStr == null || numStr.length() == 0) {
			return 0;
		}
		char[] str = numStr.toCharArray();
		return process(str, 0);
	}

	/**
	 * 	递归过程
	 * @param str
	 * @param index  当前位置上考虑 返回转化结果数
	 * @return
	 */
	private static int process(char[] str, int index) {
		if(index == str.length) {
			// numStr所有字符都考察了一遍还没有违规的 就是一种转化结果
			return 1;
		}
		if(str[index] == '0') {
			// 该位置是0字符 无法转化为字母 
			return 0;
		}
		// 要么将index位置数字转化为字母进行转化
		int ways = process(str, index + 1);
		// 要么将index与index+1位置数字转化为字母进行转化
		if(index + 1 < str.length && (str[index] - '0') * 10 + (str[index + 1] - '0') < 27) {
			ways += process(str, index + 2);
		}
		return ways;
	}
	
	public static void main(String[] args) {
		System.out.println(convertToLetterString1("305"));
		System.out.println(convertToLetterString1("7210231231232031203123"));
	}
}
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
54
55

动态规划代码：

package class19;

/**
 * -数字串转化为字符串问题
 * -规定1和A对应、2和B对应、3和C对应...26和Z对应
 * -那么一个数字字符串比如"111”就可以转化为:
 * -"AAA"、"KA"和"AK"
 * -给定一个只有数字字符组成的字符串str，返回有多少种转化结果 
 * @author yangyanchao
 *
 */
public class Test02_ConvertToLetterString {
	/**
	 * -动态规划版本
	 * @param numStr
	 * @return
	 */
	public static int convertToLetterString2(String numStr) {
		if(numStr == null || numStr.length() == 0) {
			return 0;
		}
		char[] str = numStr.toCharArray();
		int N = str.length;
		int[] dp = new int[N + 1];
		dp[N] = 1;
		for(int index = N - 1; index >= 0; index--) {
			if(str[index] != '0') {
				int ways = dp[index + 1];
				if(index + 1 < N && (str[index] - '0') * 10 + (str[index + 1] - '0') < 27) {
					ways += dp[index + 2];
				}
				dp[index] = ways;
			}
		}
		return dp[0];
	}
	
	public static void main(String[] args) {
		System.out.println(convertToLetterString2("305"));
		System.out.println(convertToLetterString2("7210231231232031203123"));
	}
}
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

# 题目三

贴纸问题

从左往右的尝试模型

给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文 arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来 返回需要至少多少张贴纸可以完成这个任务。 例子：str= "babac"，arr = {"ba","c","abcd"} ba + ba + c 3 abcd + abcd 2 abcd+ba 2 所以返回2

暴力递归不优化版本代码：

package class19;

/**
 * -贴纸问题
 * -给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
 * -arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
 * -返回需要至少多少张贴纸可以完成这个任务。
 * -例子：str= "babac"，arr = {"ba","c","abcd"}
 * -ba + ba + c  3  abcd + abcd 2  abcd+ba 2
 * -所以返回2 	
 * @author yangyanchao
 *
 */
//本题测试链接：https://leetcode.com/problems/stickers-to-spell-word
public class Test03_StickersToSpellWord {
	/**
	 * 	贴纸问题-暴力递归不优化版本
	 * @param stickers
	 * @param target
	 * @return
	 */
	public static int minStickers1(String[] stickers, String target) {
		if(stickers == null || stickers.length == 0 || target == null || target.length() == 0) {
			return 0;
		}
		int ans = process1(stickers, target);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	/**
	 * 	递归过程
	 * @param stickers
	 * @param target      剩余的目标字符串
	 * @return
	 */
	private static int process1(String[] stickers, String target) {
		if(target.length() == 0) {
			// 目标字符串是空字符串我需要0张贴纸就搞定了
			return 0;
		}
		// 目标字符串不为空，则我拿第一张贴纸来消除目标字符串
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < stickers.length; i++) {
			String rest = clearUp(stickers[i], target);
			if(rest.length() != target.length()) {
				// 消除了一些字符
				min = Math.min(min, process1(stickers, rest));
			}
		}
		return min + (min == Integer.MAX_VALUE ? 0 : 1);
	}

	/**
	 * 	使用sticker的字符清除rest字符
	 * @param sticker
	 * @param rest
	 * @return
	 */
	private static String clearUp(String sticker, String target) {
		char[] st = sticker.toCharArray();
		char[] re = target.toCharArray();
		int[] count = new int[26];
		for(char ss : re) {
			count[ss-'a']++;
		}
		for(char ss : st) {
			count[ss-'a']--;
		}
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < count.length; i++) {
			if(count[i] > 0) {
				for(int j = 0; j < count[i]; j++) {
					sb.append((char) ('a' + i));
				}
			}
		}
		return sb.toString();
	}
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

暴力递归优化版本代码：

package class19;

/**
 * -贴纸问题
 * -给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
 * -arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
 * -返回需要至少多少张贴纸可以完成这个任务。
 * -例子：str= "babac"，arr = {"ba","c","abcd"}
 * -ba + ba + c  3  abcd + abcd 2  abcd+ba 2
 * -所以返回2 	
 * @author yangyanchao
 *
 */
//本题测试链接：https://leetcode.com/problems/stickers-to-spell-word
public class Test03_StickersToSpellWord {		
	/**
	 * 	贴纸问题-暴力递归优化版本
	 * 	使用词频做stickers
	 * @param stickers
	 * @param target
	 * @return
	 */
	public static int minStickers2(String[] stickers, String target) {
		if(stickers == null || stickers.length == 0 || target == null || target.length() == 0) {
			return 0;
		}
		int N = stickers.length;
		int[][] counts = new int[N][26];
		for(int i = 0; i < N; i++) {
			char[] chars = stickers[i].toCharArray();
			for(int j = 0; j < chars.length; j++) {
				counts[i][chars[j] - 'a']++;
			}
		}
		int ans = process2(counts, target);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	/**
	 * 	使用counts除rest字符
	 * @param counts
	 * @param target
	 * @return
	 */
	private static int process2(int[][] counts, String target) {
		if(target.length() == 0) {
			return 0;
		}
		// target 做成-> 词频 targetCountcount 目标字符词频
		char[] tarChars = target.toCharArray();
		int[] targetCount = new int[26];
		for(char cha : tarChars) {
			targetCount[cha - 'a']++;
		}
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < counts.length; i++) {
			// sticker-> 词频 stickerCount 贴纸词频
			int[] stickerCount = counts[i];
			if(stickerCount[tarChars[0] - 'a'] > 0) {
				// 贴纸词频中有目标字符第一个字符  这步是重要优化与剪支
				// 减小目标字符词频
				for(int j = 0; j < stickerCount.length; j++) {
					targetCount[j] -= stickerCount[j];
				}
				StringBuilder sb = new StringBuilder();
				for(int j = 0; j < targetCount.length; j++) {
					if(targetCount[j] > 0) {
						for(int k = 0; k < targetCount[j]; k++) {
							sb.append((char) ('a' + j));
						}
					}
				}
				min = Math.min(min, process2(counts, sb.toString()));
			}
		}
		return min + (min == Integer.MAX_VALUE ? 0 : 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

记忆化搜索代码：

package class19;

import java.util.HashMap;

/**
 * -贴纸问题
 * -给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
 * -arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
 * -返回需要至少多少张贴纸可以完成这个任务。
 * -例子：str= "babac"，arr = {"ba","c","abcd"}
 * -ba + ba + c  3  abcd + abcd 2  abcd+ba 2
 * -所以返回2 	
 * @author yangyanchao
 *
 */
//本题测试链接：https://leetcode.com/problems/stickers-to-spell-word
public class Test03_StickersToSpellWord {
	/**
	 * 	贴纸问题-记忆化搜索版本
	 * 	使用词频做stickers
	 * @param stickers
	 * @param target
	 * @return
	 */
	public static int minStickers3(String[] stickers, String target) {
		if(stickers == null || stickers.length == 0 || target == null || target.length() == 0) {
			return 0;
		}
		int N = stickers.length;
		int[][] counts = new int[N][26];
		for(int i = 0; i < N; i++) {
			char[] chars = stickers[i].toCharArray();
			for(int j = 0; j < chars.length; j++) {
				counts[i][chars[j] - 'a']++;
			}
		}
		HashMap<String, Integer> dp = new HashMap<>();
		dp.put("", 0);
		int ans = process3(counts, target, dp);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	/**
	 * 	使用counts除rest字符
	 * @param counts
	 * @param target
	 * @return
	 */
	private static int process3(int[][] counts, String target, HashMap<String, Integer> dp) {
		if(dp.containsKey(target)) {
			return dp.get(target);
		}
		char[] tarChars = target.toCharArray();
		int[] targetCount = new int[26];
		for(char cha : tarChars) {
			targetCount[cha - 'a']++;
		}
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < counts.length; i++) {
			int[] stickerCount = counts[i];
			if(stickerCount[tarChars[0] - 'a'] > 0) {
				StringBuilder sb = new StringBuilder();
				for(int j = 0; j < 26; j++) {
					if(targetCount[j] > 0) {
						int nums = targetCount[j] - stickerCount[j];
						for(int k = 0; k < nums; k++) {
							sb.append((char) ('a' + j));
						}
					}
				}
				min = Math.min(min, process3(counts, sb.toString(), dp));
			}
		}
		int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
		dp.put(target, ans);
		return ans;
	}
}
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

# 题目四

最长公共子序列问题

多样本位置全对应的尝试模型

给定两个字符串str1和str2， 返回这两个字符串的最长公共子序列长度

比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k” 最长公共子序列是“123456”，所以返回长度6

暴力递归代码：

package class19;

/**
 *- 最长公共子序列问题
 *- 给定两个字符串str1和str2，
 *- 返回这两个字符串的最长公共子序列长度
 *- 比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
 *- 最长公共子序列是“123456”，所以返回长度6
 * @author yangyanchao
 *
 */
//链接：https://leetcode.com/problems/longest-common-subsequence/
public class Test04_LongestCommonSubsequence {
	
	/**
	 * 	最长公共子序列问题-暴力递归
	 * @param str1
	 * @param str2
	 * @return
	 */
	public static int longestCommonSubsequence1(String str1, String str2) {
		if(str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
			return 0;
		}
		int N = str1.length();
		int M = str2.length();
		char[] chars1 = str1.toCharArray();
		char[] chars2 = str2.toCharArray();
		return process1(chars1, chars2, N - 1, M - 1);
	}

	private static int process1(char[] chars1, char[] chars2, int n, int m) {
		// n == 0 && m == 0 -> chars1[n] == chars2[m] ? 1 : 0
		if(n == 0 && m == 0) {
			return chars1[n] == chars2[m] ? 1 : 0;
		}
		if(n == 0) {
			return chars1[n] == chars2[m] ? 1 : process1(chars1, chars2, n, m - 1);
		}
		if(m == 0) {
			return chars1[n] == chars2[m] ? 1 : process1(chars1, chars2, n - 1, m);
		}
		// 要么最长公共子序列的结尾不是是chars1[n]，但是可能是chars2[m]
		int p1 = process1(chars1, chars2, n - 1, m);
		int p2 = process1(chars1, chars2, n, m - 1);
		int p3 = chars1[n] == chars2[m] ? 1 + process1(chars1, chars2, n - 1, m - 1) : 0;
		return Math.max(p1, Math.max(p2, p3));
	}
}
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

动态规划代码：

package class19;

/**
 *- 最长公共子序列问题
 *- 给定两个字符串str1和str2，
 *- 返回这两个字符串的最长公共子序列长度
 *- 比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
 *- 最长公共子序列是“123456”，所以返回长度6
 * @author yangyanchao
 *
 */
//链接：https://leetcode.com/problems/longest-common-subsequence/
public class Test04_LongestCommonSubsequence {	
	/**
	 * 	最长公共子序列问题-动态规划
	 * @param str1
	 * @param str2
	 * @return
	 */
	public static int longestCommonSubsequence2(String str1, String str2) {
		if(str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
			return 0;
		}
		int N = str1.length();
		int M = str2.length();
		char[] chars1 = str1.toCharArray();
		char[] chars2 = str2.toCharArray();
		int [][] dp = new int[N][M];
		dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
		for(int i = 1; i < M; i++) {
			dp[0][i] = chars1[0] == chars2[i] ? 1 : dp[0][i - 1];
		}
		for(int i = 1; i < N; i++) {
			dp[i][0] = chars1[i] == chars2[0] ? 1 : dp[i - 1][0];
		}
		for(int n = 1; n < N; n++) {
			for(int m = 1; m < M; m++) {
				int p1 = dp[n - 1][m];
				int p2 = dp[n][m - 1];
				int p3 = chars1[n] == chars2[m] ? 1 + dp[n - 1][m - 1] : 0;
				dp[n][m] = Math.max(p1, Math.max(p2, p3));
			}
		}
		return dp[N - 1][M - 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

← 第20节 暴力递归到动态规划（三） →