学步园

题目：

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 (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

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.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT->
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.

思路：

这题其实是一道非常简单的动态规划（不知道为何被归为hard）。就是要找一条权值最小路径，权值即为该骑士K的当前血量。

不妨从最右下角开始考虑，由于骑士只能向右和向下，因此倒推的时候，某个格子的所需最小血量应该由且只能由他的右边和他的下边得到。

对于最右一列和最下一行的值，就只能分别由所在格子的下面一个和所在格子的右边一个得到了。

血量的计算规则：

1.如果格子为负数，则在之前计算的基础上加上该值（记住，我们是倒推，而且每一步计算的都是最小需求量，差一丁点都不行），

不然等骑士走到下一个格子的时候血量就不够了。

2.如果格子为正数，则通过之前计算的基础上减去该值，从而得到骑士走到这个格子的时候所能够有的最小生命值，因为该格子会补血；但是，骑士在这个格子开始的血量不能为0，至少为1，因此，计算的时候减去该值的结果不能小于1，否则赋值为1，即为最小需求量。

解题中使用一个同样大小的矩阵，做中间量的记录。

转换方程为：

int fromRight = w[i][j+1]-dungeon[i][j]>0?w[i][j+1]-dungeon[i][j]:1;
int fromDown = w[i+1][j]-dungeon[i][j]>0?w[i+1][j]-dungeon[i][j]:1;
w[i][j]=Math.min(fromRight,fromDown);

AC代码：

public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] w = new int[m][n];

        w[m-1][n-1] = 1-dungeon[m-1][n-1]>0?1-dungeon[m-1][n-1]:1;
        for(int i=m-2;i>=0;i--){
             w[i][n-1] = w[i+1][n-1]-dungeon[i][n-1]>0?w[i+1][n-1]-dungeon[i][n-1]:1;
        }
        for(int i=n-2;i>=0;i--)
            w[m-1][i] = w[m-1][i+1]-dungeon[m-1][i]>0?w[m-1][i+1]-dungeon[m-1][i]:1;

        for(int i=m-2;i>=0;i--){
            for(int j=n-2;j>=0;j--){
                int fromRight = w[i][j+1]-dungeon[i][j]>0?w[i][j+1]-dungeon[i][j]:1;
                int fromDown = w[i+1][j]-dungeon[i][j]>0?w[i+1][j]-dungeon[i][j]:1;
                w[i][j]=Math.min(fromRight,fromDown);
            }
        }

        return w[0][0];
    }