递归与动态规划——骑士与地下城游戏问题

Posted on | In ,

题目：给定一二维数组map，含义是一张地图。骑士只能从左上角出发，向下或向右最后到达右下角见到公主。地图中的负数代表此处有怪兽，会让骑士损失血量；地图中的正数代表此处有血瓶，能让骑士回血。要求骑士从左上角到右下角的任何位置，血量都不能少于1。问为了保证能够见到公主，骑士的初始血量是多少？

实现：动态规划，生成和地图大小一样的dp动态规划矩阵。dp[i][j]表示要到达map[i][j]前应该有的最小血量。
第一种分析方法：

  1. dp[i][j+1]表示选择向右走最终到达右下角的血量要求，则在当前(i,j)位置加完血或扣完血血量等于dp[i][j+1]即可，即dp[i][j]=dp[i][j+1]]-map[i][j]；同时要保证骑士血量至少为1，则向右走的要求为dp[i][j]=max{dp[i][j+1]]-map[i][j],1}.
  2. dp[i+1][j]表示选择向下走最终到达右下角的血量要求，则在当前(i,j)加完血或扣完血血量等于dp[i+1][j]即可。后面分析与步骤1相同。dp[i][j]=max{dp[i+1][j]]-map[i][j],1}
  3. 为了选择最优的路径，dp[i][j]=min{max{dp[i][j+1]]-map[i][j],1},max{dp[i+1][j]]-map[i][j],1}}
  4. 从上面几步可以看出，当前的值依靠下面和右边位置的值，因此计算dp矩阵是从右下角开始，从右至左、从下往上进行计算。dp[0][0]就是需要的初始血量。

第二种分析方法：这样是比较好理解，但是上面的分析方法更容易计算dp[i][j]。
有两个方向可以到达dp[i][j]:

  1. 从上边下来，则dp[i-1][j]需要保证的血量为dp[i-1][j]=dp[i][j]-map[[i-1][j]。同时为了保证最小血量为1的要求，则dp[i-1][j]=max{dp[i][j]-map[[i-1][j],1}。
  2. 从左边过来，则dp[i][j-1]=max{dp[i][j]-map[[i][j-1],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
public class KnightAndPrincess {
	public static int minDp(int[][] map) {
		if (map == null || map.length == 0 | map[0] == null || map[0].length == 0) {
			return 1;
		}
		int rows = map.length;
		int cols = map.length;
		int[][] dp = new int[rows][cols];
		int row = rows - 1;
		int col = cols - 1;
		//初始化，保证见到公主的最少血量
		/*dp[row][col] = 1; 
		if (dp[row][col] + map[row][col] < 1) { // 若遇到怪兽掉血后血量小于1
			dp[row][col] = -map[row][col] + 1; // 则重新赋值血量，保证最少血量
		}*/
		dp[row][col] = map[row][col] > 0 ? 1 : -map[row][col] + 1;
		// 为最后一行赋值
		for (int j = col - 1; j >= 0; j--) {
			/*dp[row][j] = dp[row][j + 1] - map[row][j];
			if (dp[row][j] < 1) {
				dp[row][j] = 1;
			}*/
			dp[row][j] = Math.max(dp[row][j+1]-map[row][j], 1);
		}
		// 为最后一列赋值
		for (int i = row - 1; i >= 0; i--) {
			/*dp[i][col] = dp[i + 1][col] - map[i][col];
			if (dp[i][col] < 1) {
				dp[i][col] = 1;
			}*/
			dp[i][col] = Math.max(dp[i+1][col]-map[i][col], 1);
		}
		// 为非最后一行和最后一列赋值
		for (int i = row - 1; i >= 0; i--) {
			for (int j = col -1; j >= 0; j--) {
				/*dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]) - map[i][j];
				if (dp[i][j] < 1) {
					dp[i][j] = 1;
				}*/
				int right = Math.max(dp[i][j+1]-map[i][j], 1);
				int down = Math.max(dp[i+1][j]-map[i][j], 1);
				dp[i][j] = Math.min(right, down);
			}
		}
		System.out.println("dp动态规划矩阵：");
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j< cols; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
		return dp[0][0];
	}
	//Test
	public static void main(String[] args) {
		int[][] map = {
				{-2,-3,3},
				{-5,-10,1},
				{0,30,-5}
		};
		System.out.println("初始血量为：" + minDp(map));
	}
}

输出：

1
2
3
4
5
dp动态规划矩阵：
7 5 2 
6 11 5 
1 1 6 
初始血量为：7