ShiYu

# 第22节 暴力递归到动态规划（五）

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

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

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

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

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

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

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

# 题目一

英雄打怪兽问题

给定3个参数，N，M，K 怪兽有N滴血，等着英雄来砍自己 英雄每一次打击，都会让怪兽流失[0~M]的血量 到底流失多少？每一次在[0~M]上等概率的获得一个值 求K次打击之后，英雄把怪兽砍死的概率

业务限制模型

思路：

  • 总情况数为M+1^K
  • 求出英雄把怪兽砍死的方法数然后与怪兽相除

暴力递归代码：

package class22;

/**
 * - 英雄打怪兽问题
 * - 给定3个参数，N，M，K
 * - 怪兽有N滴血，等着英雄来砍自己
 * - 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * - 到底流失多少？每一次在[0~M]上等概率的获得一个值
 * - 求K次打击之后，英雄把怪兽砍死的概率
 * @author yangyanchao
 *
 */
public class Test01_KillMonster {
	public static double chances(int N, int M, int K) {
		if (N < 1 || M < 1 || K < 1) {
			return 0;
		}
		long all = (long) Math.pow(M + 1, K);
		long kill = process1(N, M, K);
		return (double) ((double) kill / (double) all);
	}

	private static long process1(int hp, int m, int times) {
		if(times == 0) {
			return hp <= 0 ? 1 : 0;
		}
		if(hp <= 0) {
			return (long) Math.pow(m + 1, times);
		}
		int ways = 0;
		for(int i = 0; i <= m; i++) {
			ways += process1(hp - i, m, times -1);
		}
		return ways;
	}
}
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

动态规划代码：

package class22;

/**
 * - 英雄打怪兽问题
 * - 给定3个参数，N，M，K
 * - 怪兽有N滴血，等着英雄来砍自己
 * - 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * - 到底流失多少？每一次在[0~M]上等概率的获得一个值
 * - 求K次打击之后，英雄把怪兽砍死的概率
 * @author yangyanchao
 *
 */
public class Test01_KillMonster {
	public static double dp1(int N, int M, int K) {
		if (N < 1 || M < 1 || K < 1) {
			return 0;
		}
		long all = (long) Math.pow(M + 1, K);
		int[][] dp = new int[N + 1][K + 1];
		dp[0][0] = 1;
		for(int times = 1; times <= K; times++) {
			for(int hp = 0; hp <= N; hp++) {
				for(int i = 0; i <= M; i++) {
					if(hp - i > 0) {
						dp[hp][times] += dp[hp - i][times -1];
					} else {
						dp[hp][times] += (long) Math.pow(M + 1, times - 1);
					}
				}
			}
		}
		long kill = dp[N][K];
		return (double) ((double) kill / (double) all);
	}
}
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

动态规划斜率(临近位置观察法)优化代码：

package class22;

/**
 * - 英雄打怪兽问题
 * - 给定3个参数，N，M，K
 * - 怪兽有N滴血，等着英雄来砍自己
 * - 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * - 到底流失多少？每一次在[0~M]上等概率的获得一个值
 * - 求K次打击之后，英雄把怪兽砍死的概率
 * @author yangyanchao
 *
 */
public class Test01_KillMonster {
	public static double dp2(int N, int M, int K) {
		if (N < 1 || M < 1 || K < 1) {
			return 0;
		}
		long all = (long) Math.pow(M + 1, K);
		long[][] dp = new long[N + 1][K + 1];
		dp[0][0] = 1;
		for(int times = 1; times <= K; times++) {
			dp[0][times] = (long) Math.pow(M + 1, times);
			for(int hp = 1; hp <= N; hp++) {
				dp[hp][times] = dp[hp][times - 1] + dp[hp - 1][times];
				if(hp - (M + 1) >= 0) {
					dp[hp][times] -= dp[hp - (M + 1)][times - 1];
				} else {
					dp[hp][times] -= (long) Math.pow(M + 1, times - 1);
				}
			}
		}
		long kill = dp[N][K];
		return (double) ((double) kill / (double) all);
	}
}
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

# 题目二

最少找零问题

arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。 每个值都认为是一种面值，且认为张数是无限的。 返回组成aim的最少货币数

从左到右模型

暴力递归代码：

package class22;

/**
 * - 最少找零问题
 * - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * - 每个值都认为是一种面值，且认为张数是无限的。
 * - 返回组成aim的最少货币数
 * @author yangyanchao
 *
 */
public class Test02_MinCoinsNoLimit {
	public static int minCoins(int[] arr, int aim) {
		if(aim < 1 || arr == null || arr.length == 0) {
			return 0;
		}
		return process1(arr, 0, aim);
	}

	private static int process1(int[] arr, int index, int rest) {
		if(index == arr.length) {
			return rest == 0 ? 0 : Integer.MAX_VALUE;
		}
		int minAim = Integer.MAX_VALUE;
		for(int zhang = 0; zhang * arr[index] <= rest; zhang++) {
			int next = process1(arr, index + 1, rest - zhang * arr[index]);
			if(next != Integer.MAX_VALUE) {
				minAim = Math.min(minAim, zhang + next);
			}
		}
		return minAim;
	}
}
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

动态规划代码：

package class22;

/**
 * - 最少找零问题
 * - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * - 每个值都认为是一种面值，且认为张数是无限的。
 * - 返回组成aim的最少货币数
 * @author yangyanchao
 *
 */
public class Test02_MinCoinsNoLimit {
	public static int dp1(int[] arr, int aim) {
		if(aim < 1 || arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 0;
		for(int i = 1; i <= aim; i++) {
			dp[N][i] = Integer.MAX_VALUE;
		}
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= aim; rest++) {
				dp[index][rest] = Integer.MAX_VALUE;
				for(int zhang = 0; zhang * arr[index] <= rest; zhang++) {
					int next = dp[index + 1][rest - zhang * arr[index]];
					if(next != Integer.MAX_VALUE) {
						dp[index][rest] = Math.min(dp[index][rest], zhang + next);
					}
				}
			}
		}
		return dp[0][aim];
	}
}
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

动态规划斜率(临近位置观察法)优化代码：

package class22;

/**
 * - 最少找零问题
 * - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * - 每个值都认为是一种面值，且认为张数是无限的。
 * - 返回组成aim的最少货币数
 * @author yangyanchao
 *
 */
public class Test02_MinCoinsNoLimit {
	public static int dp2(int[] arr, int aim) {
		if(aim < 1 || arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 0;
		for(int i = 1; i <= aim; i++) {
			dp[N][i] = Integer.MAX_VALUE;
		}
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= aim; rest++) {
				dp[index][rest] = dp[index + 1][rest];
				if(rest - arr[index] >= 0 && dp[index][rest - arr[index]] != Integer.MAX_VALUE) {
					dp[index][rest] = Math.min(dp[index][rest], dp[index][rest - arr[index]] + 1);
				}
			}
		}
		return dp[0][aim];
	}
}
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

# 题目三

数字裂开问题

给定一个正数n，求n的裂开方法数， 规定：后面的数不能比前面的数小 比如4的裂开方法有： 1+1+1+1、1+1+2、1+3、2+2、4 5种，所以返回5

从左到右模型

暴力递归代码：

package class22;

/**
 * - 数字裂开问题
 * - 给定一个正数n，求n的裂开方法数，
 * - 规定：后面的数不能比前面的数小
 * - 比如4的裂开方法有：
 * - 1+1+1+1、1+1+2、1+3、2+2、4
 * - 5种，所以返回5
 * @author yangyanchao
 *
 */
public class Test03_SplitNumber {
	public static int ways1(int n) {
		if (n < 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		return process1(1, n);
	}

	/**
	 * @param pre  前面的数 后面的数要比pre大
	 * @param rest 还要裂开的数
	 * @return
	 */
	private static int process1(int pre, int rest) {
		if(rest < 0) {
			return 0;
		}
		if(rest == 0) {
			return 1;
		}
		int ways = 0;
		for(int num = pre; num <= rest; num++) {
			ways += process1(num, rest - num);
		}
		return ways;
	}
	
	public static void main(String[] args) {
		int test = 39;
		System.out.println(ways1(test));
	}
}
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

动态规划代码：

package class22;

/**
 * - 数字裂开问题
 * - 给定一个正数n，求n的裂开方法数，
 * - 规定：后面的数不能比前面的数小
 * - 比如4的裂开方法有：
 * - 1+1+1+1、1+1+2、1+3、2+2、4
 * - 5种，所以返回5
 * @author yangyanchao
 *
 */
public class Test03_SplitNumber {
	
	public static int dp1(int n) {
		if (n < 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		int[][] dp = new int[n + 1][n + 1];
		for (int pre = 1; pre <= n; pre++) {
			dp[pre][0] = 1;
			dp[pre][pre] = 1;
		}
		for(int pre = n; pre >= 0; pre--) {
			for(int rest = pre + 1; rest <= n; rest++) {
				for(int num = pre; num <= rest; num++) {
					dp[pre][rest] += dp[num][rest - num];
				}
			}
		}
		return dp[1][n];
	}
	
	public static void main(String[] args) {
		int test = 39;
		System.out.println(dp1(test));
	}
}
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

动态规划斜率(临近位置观察法)优化代码：

package class22;

/**
 * - 数字裂开问题
 * - 给定一个正数n，求n的裂开方法数，
 * - 规定：后面的数不能比前面的数小
 * - 比如4的裂开方法有：
 * - 1+1+1+1、1+1+2、1+3、2+2、4
 * - 5种，所以返回5
 * @author yangyanchao
 *
 */
public class Test03_SplitNumber {
	
	public static int dp2(int n) {
		if (n < 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		int[][] dp = new int[n + 1][n + 1];
		for (int pre = 1; pre <= n; pre++) {
			dp[pre][0] = 1;
			dp[pre][pre] = 1;
		}
		for (int pre = n - 1; pre >= 1; pre--) {
			for (int rest = pre + 1; rest <= n; rest++) {
				dp[pre][rest] = dp[pre + 1][rest];
				dp[pre][rest] += dp[pre][rest - pre];
			}
		}
		return dp[1][n];
	}
	
	public static void main(String[] args) {
		int test = 39;
		System.out.println(dp2(test));
	}
}
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

← 第23节 暴力递归到动态规划（六） →