ShiYu

# 第21节 暴力递归到动态规划（四）

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

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

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

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

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

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

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

# 题目一

最短路径问题

给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和 返回最小距离累加和

业务限制模型

暴力递归代码：

package class21;

/**
 * - 最短路径问题
 * - 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
 * - 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
 * - 返回最小距离累加和
 * @author yangyanchao
 *
 */
public class Test01_MinPathSum {
	
	public static int minPathSum1(int[][] matrix) {
		if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
			return 0;
		}
		int row = matrix.length;
		int col = matrix[0].length;
		return process1(matrix, row - 1, col - 1, 0, 0);
	}
	
	public static int process1(int[][] matrix, int tRow, int tCol, int sRow, int sCol) {
		if(sRow == tRow && sCol == tCol) {
			return matrix[sRow][sCol];
		}
		if(sRow == tRow && sCol < tCol) {
			// 只能向右了
			return matrix[sRow][sCol] + process1(matrix, tRow, tCol, sRow, sCol + 1);
		}
		if(sRow < tRow && sCol == tCol) {
			// 只能向下了
			return matrix[sRow][sCol] + process1(matrix, tRow, tCol, sRow + 1, sCol);
		}
		// 向下
		int p1 = process1(matrix, tRow, tCol, sRow + 1, sCol);
		// 向右
		int p2 = process1(matrix, tRow, tCol, sRow, sCol + 1);
		return Math.min(p1, p2) + matrix[sRow][sCol];
	}
}
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

动态规划代码：

package class21;

/**
 * - 最短路径问题
 * - 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
 * - 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
 * - 返回最小距离累加和
 * @author yangyanchao
 *
 */
public class Test01_MinPathSum {
	public static int dp1(int[][] matrix) {
		if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
			return 0;
		}
		int row = matrix.length - 1;
		int col = matrix[0].length - 1;
		int[][] dp = new int[row + 1][col + 1];
		dp[row][col] = matrix[row][col];
		for(int sCol = col - 1; sCol >= 0; sCol--) {
			dp[row][sCol] = matrix[row][sCol] + dp[row][sCol + 1];
		}
		for(int sRow = row - 1; sRow >= 0; sRow--) {
			dp[sRow][col] = matrix[sRow][col] + dp[sRow + 1][col];
		}
		for(int sRow = row - 1; sRow >= 0; sRow--) {
			for(int sCol = col - 1; sCol >= 0; sCol--) {
				dp[sRow][sCol] = matrix[sRow][sCol] + Math.min(dp[sRow][sCol + 1], dp[sRow + 1][sCol]);
			}
		}
		return dp[0][0];
	}
	

}
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

空间压缩优化代码：发现可以压缩空间将二维dp数组用一维代替

通过观察表结构的依赖是自底向上、自右向左的所以可以用一维数组自右向左的存储一行数据，最终使用0号位置数据返回

package class21;

/**
 * - 最短路径问题
 * - 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
 * - 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
 * - 返回最小距离累加和
 * @author yangyanchao
 *
 */
public class Test01_MinPathSum {
	public static int dp2(int[][] matrix) {
		if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
			return 0;
		}
		int row = matrix.length - 1;
		int col = matrix[0].length - 1;
		int[] dp = new int[col + 1];
		dp[col] = matrix[row][col];
		for(int sCol = col - 1; sCol >= 0; sCol--) {
			dp[sCol] = matrix[row][sCol] + dp[sCol + 1];
		}
		for(int sRow = row - 1; sRow >= 0; sRow--) {
			dp[col] += matrix[sRow][col];
			for(int sCol = col- 1; sCol >= 0; sCol--) {
				dp[sCol] = matrix[sRow][sCol] + Math.min(dp[sCol + 1], dp[sCol]);
			}
		}
		return dp[0];
	}
}
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

# 题目二

找零方法数问题一不同货币

arr是货币数组，其中的值都是正数。再给定一个正数aim。 每个值都认为是一张货币， 即便是值相同的货币也认为每一张都是不同的， 返回组成aim的方法数 例如：arr = {1,1,1}，aim = 2 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2 一共就3种方法，所以返回3

从左往右模型

暴力递归代码：

package class21;

/**
 * - 找零方法数问题一不同货币
 * - arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * - 每个值都认为是一张货币，
 * - 即便是值相同的货币也认为每一张都是不同的，
 * - 返回组成aim的方法数
 * - 例如：arr = {1,1,1}，aim = 2
 * - 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test02_CoinsWayEveryPaperDifferent {
	public static int ways(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		return process1(arr, 0, aim);
	}

	private static int process1(int[] arr, int index, int rest) {
		if(rest < 0) {
			return 0;
		}
		if(index == arr.length) {
			return rest == 0 ? 1 : 0;
		}
		int ways = 0;
		// 要
		ways += process1(arr, index + 1, rest - arr[index]);
		// 不要
		ways += process1(arr, index + 1, rest);
		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
38

动态规划代码：

package class21;

/**
 * - 找零方法数问题一不同货币
 * - arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * - 每个值都认为是一张货币，
 * - 即便是值相同的货币也认为每一张都是不同的，
 * - 返回组成aim的方法数
 * - 例如：arr = {1,1,1}，aim = 2
 * - 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test02_CoinsWayEveryPaperDifferent {
	
	public static int dp(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 1;
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= aim; rest++) {
				if(arr[index] <= rest) {
					dp[index][rest] += dp[index + 1][rest - arr[index]];
				}
				dp[index][rest] += dp[index + 1][rest];
			}
		}
		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

# 题目三

找零方法数问题一同种货币张数无限

arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。 每个值都认为是一种面值，且认为张数是无限的。 返回组成aim的方法数 例如：arr = {1,2}，aim = 4 方法如下：1+1+1+1、1+1+2、2+2 一共就3种方法，所以返回3

暴力递归代码：

package class21;

/**
 * - 找零方法数问题一同种货币张数无限
 * - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * - 每个值都认为是一种面值，且认为张数是无限的。
 * - 返回组成aim的方法数
 * - 例如：arr = {1,2}，aim = 4
 * - 方法如下：1+1+1+1、1+1+2、2+2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test03_CoinsWayNoLimit {
	public static int ways(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		return process1(arr, 0, aim);
	}

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

动态规划代码：

package class21;

/**
 * - 找零方法数问题一同种货币张数无限
 * - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * - 每个值都认为是一种面值，且认为张数是无限的。
 * - 返回组成aim的方法数
 * - 例如：arr = {1,2}，aim = 4
 * - 方法如下：1+1+1+1、1+1+2、2+2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test03_CoinsWayNoLimit {
	
	
	public static int dp(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 1;
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= aim; rest++) {
				for(int zhang = 0; zhang * arr[index] <= rest; zhang++) {
					dp[index][rest] += dp[index + 1][rest - zhang * arr[index]];
				}
			}
		}
		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

动态规划斜率(临近位置观察法)优化代码：状态化简 将枚举行为优化掉

通过位置观察普遍位置dp[index][rest] 依赖下边位置dp[index + 1][rest]与dp[index][rest - arr[index]]

之前：

普遍位置dp[index][rest]=dp[index + 1][rest]+dp[index + 1][rest - arr[index]] +dp[index + 1][rest - 1 * arr[index]]...

而dp[index][rest - arr[index]]=dp[index + 1][rest - arr[index]] +dp[index + 1][rest - 1 * arr[index]]...

所以推出：dp[index][rest]=dp[index + 1][rest]+dp[index][rest - arr[index]]

package class21;

/**
 * - 找零方法数问题一同种货币张数无限
 * - arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * - 每个值都认为是一种面值，且认为张数是无限的。
 * - 返回组成aim的方法数
 * - 例如：arr = {1,2}，aim = 4
 * - 方法如下：1+1+1+1、1+1+2、2+2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test03_CoinsWayNoLimit {
	
	public static int dp1(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 1;
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= aim; rest++) {
				dp[index][rest] += dp[index + 1][rest];
				if(arr[index] <= rest) {
					dp[index][rest] += dp[index][rest - arr[index]];
				}
			}
		}
		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

# 题目四

找零方法数问题一同种货币张数有限

arr是货币数组，其中的值都是正数。再给定一个正数aim。 每个值都认为是一张货币， 认为值相同的货币没有任何不同， 返回组成aim的方法数 例如：arr = {1,2,1,1,2,1,2}，aim = 4 方法：1+1+1+1、1+1+2、2+2 一共就3种方法，所以返回3

暴力递归代码：

package class21;

import java.util.HashMap;
import java.util.Map.Entry;

/**
 * - 找零方法数问题一同种货币张数有限
 * - arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * - 每个值都认为是一张货币，
 * - 认为值相同的货币没有任何不同，
 * - 返回组成aim的方法数
 * - 例如：arr = {1,2,1,1,2,1,2}，aim = 4
 * - 方法：1+1+1+1、1+1+2、2+2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test04_CoinsWaySameValueSamePapper {
	
	public static class Info {
		public int[] coins;
		public int[] zhangs;

		public Info(int[] c, int[] z) {
			coins = c;
			zhangs = z;
		}
	}

	public static Info getInfo(int[] arr) {
		HashMap<Integer, Integer> counts = new HashMap<>();
		for (int value : arr) {
			if (!counts.containsKey(value)) {
				counts.put(value, 1);
			} else {
				counts.put(value, counts.get(value) + 1);
			}
		}
		int N = counts.size();
		int[] coins = new int[N];
		int[] zhangs = new int[N];
		int index = 0;
		for (Entry<Integer, Integer> entry : counts.entrySet()) {
			coins[index] = entry.getKey();
			zhangs[index++] = entry.getValue();
		}
		return new Info(coins, zhangs);
	}
	
	public static int ways(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		Info info = getInfo(arr);
		return process1(info.coins, info.zhangs, 0, aim);
	}

	private static int process1(int[] coins, int[] zhangs, int index, int rest) {
		if(index == coins.length) {
			return rest == 0 ? 1 : 0;
		}
		int ways = 0;
		for(int zhang = 0; coins[index] * zhang <= rest && zhang <= zhangs[index]; zhang++) {
			ways += process1(coins, zhangs, index + 1, rest - coins[index] * zhang);
		}
		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
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

动态规划代码：

package class21;

import java.util.HashMap;
import java.util.Map.Entry;

/**
 * - 找零方法数问题一同种货币张数有限
 * - arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * - 每个值都认为是一张货币，
 * - 认为值相同的货币没有任何不同，
 * - 返回组成aim的方法数
 * - 例如：arr = {1,2,1,1,2,1,2}，aim = 4
 * - 方法：1+1+1+1、1+1+2、2+2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test04_CoinsWaySameValueSamePapper {
	
	public static class Info {
		public int[] coins;
		public int[] zhangs;

		public Info(int[] c, int[] z) {
			coins = c;
			zhangs = z;
		}
	}

	public static Info getInfo(int[] arr) {
		HashMap<Integer, Integer> counts = new HashMap<>();
		for (int value : arr) {
			if (!counts.containsKey(value)) {
				counts.put(value, 1);
			} else {
				counts.put(value, counts.get(value) + 1);
			}
		}
		int N = counts.size();
		int[] coins = new int[N];
		int[] zhangs = new int[N];
		int index = 0;
		for (Entry<Integer, Integer> entry : counts.entrySet()) {
			coins[index] = entry.getKey();
			zhangs[index++] = entry.getValue();
		}
		return new Info(coins, zhangs);
	}
	
	public static int dp1(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		Info info = getInfo(arr);
		int[] coins = info.coins;
		int[] zhangs = info.zhangs;
		int N = coins.length;
		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 1;
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= aim; rest++) {
				for(int zhang = 0; coins[index] * zhang <= rest && zhang <= zhangs[index]; zhang++) {
					dp[index][rest] += dp[index + 1][rest - coins[index] * zhang];
				}
			}
		}
		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
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

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

通过位置观察

dp[index][rest] += dp[index + 1][rest];
// 普遍位置dp[index][rest] 依赖下边位置dp[index + 1][rest]
if(coins[index] <= rest) {
    // 普遍位置dp[index][rest] 依赖左边dp[index][rest - coins[index]] 
    // 但是多了dp[index + 1][rest - (zhangs[index] + 1) * coins[index]]
    dp[index][rest] += dp[index][rest - coins[index]];
}
if((zhangs[index] + 1) * coins[index] <= rest) {
    // 减掉dp[index + 1][rest - (zhangs[index] + 1) * coins[index]]
    dp[index][rest] -= dp[index + 1][rest - (zhangs[index] + 1) * coins[index]];
}
1
2
3
4
5
6
7
8
9
10
11
package class21;

import java.util.HashMap;
import java.util.Map.Entry;

/**
 * - 找零方法数问题一同种货币张数有限
 * - arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * - 每个值都认为是一张货币，
 * - 认为值相同的货币没有任何不同，
 * - 返回组成aim的方法数
 * - 例如：arr = {1,2,1,1,2,1,2}，aim = 4
 * - 方法：1+1+1+1、1+1+2、2+2
 * - 一共就3种方法，所以返回3
 * @author yangyanchao
 *
 */
public class Test04_CoinsWaySameValueSamePapper {
	
	public static class Info {
		public int[] coins;
		public int[] zhangs;

		public Info(int[] c, int[] z) {
			coins = c;
			zhangs = z;
		}
	}

	public static Info getInfo(int[] arr) {
		HashMap<Integer, Integer> counts = new HashMap<>();
		for (int value : arr) {
			if (!counts.containsKey(value)) {
				counts.put(value, 1);
			} else {
				counts.put(value, counts.get(value) + 1);
			}
		}
		int N = counts.size();
		int[] coins = new int[N];
		int[] zhangs = new int[N];
		int index = 0;
		for (Entry<Integer, Integer> entry : counts.entrySet()) {
			coins[index] = entry.getKey();
			zhangs[index++] = entry.getValue();
		}
		return new Info(coins, zhangs);
	}
	
	public static int dp2(int[] arr, int aim) {
		if(aim < 0 || arr == null || arr.length == 0) {
			return 0;
		}
		Info info = getInfo(arr);
		int[] coins = info.coins;
		int[] zhangs = info.zhangs;
		int N = coins.length;
		int[][] dp = new int[N + 1][aim + 1];
		dp[N][0] = 1;
		for(int index = N - 1; index >= 0; index--) {
			for(int rest = 0; rest <= aim; rest++) {
				dp[index][rest] += dp[index + 1][rest];
				if(coins[index] <= rest) {
					dp[index][rest] += dp[index][rest - coins[index]];
				}
				if((zhangs[index] + 1) * coins[index] <= rest) {
					dp[index][rest] -= dp[index + 1][rest - (zhangs[index] + 1) * coins[index]];
				}
			}
		}
		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
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

# 题目五

醉汉存活概率问题

给定5个参数，N，M，row，col，k 表示在NM的区域上，醉汉Bob初始在(row,col)位置 Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位 任何时候Bob只要离开NM的区域，就直接死亡 返回k步之后，Bob还在N*M的区域的概率

思路：

  • Bob每走一步会有4个方向的分支，所以Bob走了k步后总的可能性为4^k==>>Math.pow(4, k);

  • 知道了总可能性，只要求出Bob还在N*M的区域的方法数后，与总可能性相除即得出概率

暴力递归代码：

package class21;

/**
 * - 醉汉存活概率问题
 * - 给定5个参数，N，M，row，col，k
 * - 表示在N*M的区域上，醉汉Bob初始在(row,col)位置
 * - Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
 * - 任何时候Bob只要离开N*M的区域，就直接死亡
 * - 返回k步之后，Bob还在N*M的区域的概率
 * @author yangyanchao
 *
 */
public class Test05_BobDie {
	public static double chances(int N, int M, int row, int col, int k) {
		if(N < 0 || M < 0 || row < 0 || col < 0 || k < 0) {
			return -1;
		}
		return (double)(process1(N, M, row, col, k) / Math.pow(4, k));
	}

	private static long process1(int n, int m, int row, int col, int rest) {
		if(row < 0 || row == n || col < 0 || col == m) {
			return 0;
		}
		if(rest == 0) {
			return 1;
		}
		int ways = 0;
		// 上
		ways += process1(n, m, row - 1, col, rest - 1);
		// 下
		ways += process1(n, m, row + 1, col, rest - 1);
		// 左
		ways += process1(n, m, row, col - 1, rest - 1);
		// 右
		ways += process1(n, m, row, col + 1, rest - 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
38
39
40

动态规划代码：

package class21;

/**
 * - 醉汉存活概率问题
 * - 给定5个参数，N，M，row，col，k
 * - 表示在N*M的区域上，醉汉Bob初始在(row,col)位置
 * - Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
 * - 任何时候Bob只要离开N*M的区域，就直接死亡
 * - 返回k步之后，Bob还在N*M的区域的概率
 * @author yangyanchao
 *
 */
public class Test05_BobDie {
	public static double dp(int N, int M, int row1, int col1, int k) {
		int[][][] dp = new int[N][M][k + 1];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				dp[i][j][0] = 1;
			}
		}
		for(int rest = 1; rest <= k; rest++) {
			for(int row = 0; row < N; row++) {
				for(int col = 0; col < M; col++) {
					dp[row][col][rest] += picks(N, M, row - 1, col, rest - 1, dp);
					dp[row][col][rest] += picks(N, M, row + 1, col, rest - 1, dp);
					dp[row][col][rest] += picks(N, M, row, col - 1, rest - 1, dp);
					dp[row][col][rest] += picks(N, M, row, col + 1, rest - 1, dp);
				}
			}
		}
		
		return (double)(dp[row1][col1][k] / Math.pow(4, k));
	}
	private static int picks(int n, int m, int row, int col, int rest, int[][][] dp) {
		if(row < 0 || row == n || col < 0 || col == m) {
			return 0;
		}
		return dp[row][col][rest];
	}
}
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

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