骑士救公主

题目描述:一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

示例:

-1	-2	3
-1	0	0
-3	-3	-2(P)

讲解:这题也是一个动态规划类型的题目,但是是有陷阱的,我们来分析一下

有了前面的基础,我们这里也可以定义出一个dp[i][j],代表K从左上角出发,到达P所需要的最小血量。这样设置dp[][]后,我们就可以明白dp[m-1][n-1] 就是我们要求得的解。

照着上面这个思路,我们可以自己画一下dp[][]这个表格,画出来的结果应该是:

2	4	4
3	3	3
6	6	5

但是我们自己试一试,沿着路线 : -1 > -2 > 3 > 0 > -2(P) 这样走的话,骑士只需要 4 点血就足够了,我们上面分析的dp表是有误的。

那么误差是在哪里呢?在这个例子中,我们得到dp[2][2]是从dp[1][2]和dp[2][1]中求最小值然后加上P点所在位置要减去的值得出的。其实,在这两者中求最小值是不够的,我们还需要的是,到达这两个位置时K目前的血量是多少,为什么要得到这个?是因为有存在加血的格子,上面的例子中我们在路线 -1 > -2 > 3 > 0 > -2(P) 中,走完 +3血的格子后剩余血量是4(走到此格子要求起始血量最少为4) ,那么这时候再走任意一个格子(比如说-5血的格子)我们所需要的起始血量就是6,而不是9 = 4(起始最少血量)+5(走格子扣的血)

那么这里我们就可以明确一点 : 我们需要的是K到达dp[i][j]目前还剩多少血。这也是我们的问题所在 : 某一个格子的数值,不仅需要前面的计算结果,还要知道这个结果是如何计算出的。这种情况叫做后效性

后效性: 就是某个状态之后要做的决策会受之前的状态及决策的影响。

而我们动态规划算法的前提条件就是无后效性

现在我们就需要从头开始将dp[i][j]的描述换一种样子: 它表示从右下角到达这个位置最少需要多少血。

我们假设骑士从P出发,到达第一个格子对应的dp[0][0]就是所需要的最少血量

这样我们再画dp表格 :

4(K)	3	1
4	3	3
9	6	3(P)

现在我们是可以得到正确的结果的,将dp表格的含义一变,后效性就消失了;也就是只要明确两个格子取最小值,不需要明确两个格子如何计算出的。

现在就可以分析状态转移方程 : 对于一个格子dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - n[i][j] ; 但是还有一点是,如果某个格子是加血的, 那么 dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - n[i][j] 就可能是负数 , 这时候应该取1。还有一点是边界情况 : 在最上面的例子中, dp[0][2] 应该找 dp[1][2]和dp[0][3]的最小值再减n[0][2] ,可是这个表中是没有dp[0][3]的情况的,所以我们要把这些地方设置为无穷大,这样取最小值的时候就不会选择这些格子。还有一个是dp[2][2],按照刚才的情况,开始这里取最小值的时候会从两个无穷大中取一个,这样肯定不行,我们要把dp[2][3]和dp[3][2]都设置为1,这样就能处理好边界情况。下面是代码示例:

public class solution {
    public static void main(String[] args) {
        // Example
        int[][] dungeon = {
                {-2, -3, 3},
                {-5, -10, 1},
                {10, 30, -5}
        };
        solution solution = new solution();
        int i = solution.calculateMinimumHP(dungeon);
        System.out.println(i);  //OutPut: 7
    }
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        dp[m][n-1] = dp[m-1][n] = 1;

        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                int min_hp = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, min_hp);
            }
        }
        return dp[0][0];
    }
}