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.-2 (K)    -3    3-5    -10    110    30    -5 (P)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.

這是典型的思想大于行動的題目，想好了，就寥寥幾段代碼就搞定了。

這道題顯然是一道DP的題目，DP題目關鍵就是兩點：1. 維護量； 2. 遞歸方程

dp[i][j]表示進入這個格子后保證knight不會死所需要的進入這個格子之前最小HP。以最后格子為例，如果格子的值為負，那么進入這個格子之前knight需要有的最小HP是-dungeon[i][j] + 1.如果格子的值非負，那么最小HP需求就是1.

這里可以看出DP的方向是從最右下角開始一直到左上角。首先dp[m-1][n-1] = Math.max(1, -dungeon[m-1][n-1] + 1).

然后需要generalize，可以發現上面這個式子最右邊那個1表示的是：進入這個格子之后的HP值。那么對于一般格子，這里就可以替換為進入下一個格子所需最小HP。可以往下走也可以往右走。

因為是從最右下角的格子往前面推，所以dp[i][j]表示的進入某個格子的最小HP是能夠保證他走到最右下角的。也是因為有了這個保證，我們選往右還是往下根據dp[i+1][j] < dp[i][j+1] ?

遞歸方程是dp[i][j] = Math.max(1, - dungeon[i][j] +Math.min(dp[i+1][j], dp[i][j+1])).

 1 public class Solution { 2     public int calculateMinimumHP(int[][] dungeon) { 3         int m = dungeon.length; 4         int n = dungeon[0].length; 5         if (m == 0) return 0; 6         int[][] res = new int[m][n]; 7         res[m-1][n-1] = Math.max(1, -dungeon[m-1][n-1]+1); 8         for (int i=m-2; i>=0; i--) { 9             res[i][n-1] = Math.max(1, -dungeon[i][n-1]+res[i+1][n-1]);10         }11         for (int j=n-2; j>=0; j--) {12             res[m-1][j] = Math.max(1, -dungeon[m-1][j]+res[m-1][j+1]);13         }14         for (int i=m-2; i>=0; i--) {15             for (int j=n-2; j>=0; j--) {16                 res[i][j] = Math.max(1, -dungeon[i][j]+Math.min(res[i+1][j], res[i][j+1]));17             }18         }19         return res[0][0];20     }21 }