Description

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negativeintegers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positiveintegers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

Example

Given the dungeon below, the initial health of the knight must be at least7if he follows the optimal pathRIGHT-> RIGHT -> DOWN -> DOWN.

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Solution

这题要是从(0, 0)点开始遍历就很麻烦，不仅要考虑已经遍历过的点，而且要考虑遍历剩下的点最少需要多少。
反过来从(n - 1, m - 1)开始遍历就容易很多。思路是：再往前走一步所需要的最少health已经知道了，假设是prev，要求当前这点需要的最小health cur，cur应该满足cur + cur value > prev，所以prev如果小于cur value的话，只需要起始一点血就可以走过去，如果prev大于cur value，需要prev - cur value那么多血才能保证走了一步过去之后血量满足prev
所以状态方程就是 cur = Math.max(pre - cur value, 1)
在(n - 1, m - 1)的初始状态是matrix[n - 1][m - 1] >= 0 ? 1 : Math.abs(matrix[n - 1][m - 1]) + 1即Math.max(1 - matrix[n - 1][m - 1], 1)
为什么总要是跟1比较呢，因为走上这个方阵王子自己总要自带1点血啊，所以最少需要1点血

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0] == null || dungeon[0].length == 0) {
            return 0;
        }

        int n = dungeon.length;
        int m = dungeon[0].length;
        dungeon[n - 1][m - 1] = Math.max(1 - dungeon[n - 1][m - 1], 1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (i == n - 1 && j == m - 1) {
                    continue;
                }

                int down = Integer.MAX_VALUE;
                int right = Integer.MAX_VALUE;
                if (i < n - 1) {
                    down = Math.max(dungeon[i + 1][j] - dungeon[i][j], 1);
                }

                if (j < m - 1) {
                    right = Math.max(dungeon[i][j + 1] - dungeon[i][j], 1);
                }

                dungeon[i][j] = Math.min(down, right);
            }
        }

        return dungeon[0][0];
    }
}