@@ -47,7 +47,6 @@ Then, let us decide what the health should be at least when leaving room (i, j).
4747
4848Take D[0][0] and we are good to go. Also, like many other "table-filling" problems, the 2D array D can be replaced with a 1D "rolling" array here.
4949 */
50-
5150public class Solution {
5251public int calculateMinimumHP (int [][]dungeon ) {
5352int M =dungeon .length ;
@@ -56,17 +55,17 @@ public int calculateMinimumHP(int[][] dungeon) {
5655int [][]dp =new int [M ][N ];
5756dp [M -1 ][N -1 ] =1 -Math .min (0 ,dungeon [M -1 ][N -1 ]);
5857for (int i =M -2 ;i >=0 ; --i ) {
59- if (dp [i +1 ][N -1 ] -dungeon [i ][N -1 ] <0 )dp [i ][N -1 ] =1 ;
58+ if (dp [i +1 ][N -1 ] -dungeon [i ][N -1 ] <= 0 )dp [i ][N -1 ] =1 ;
6059else dp [i ][N -1 ] =dp [i +1 ][N -1 ] -dungeon [i ][N -1 ];
6160 }
6261for (int j =N -2 ;j >=0 ; --j ) {
63- if (dp [M -1 ][j +1 ] -dungeon [M -1 ][j ] <0 )dp [M -1 ][j ] =1 ;
62+ if (dp [M -1 ][j +1 ] -dungeon [M -1 ][j ] <= 0 )dp [M -1 ][j ] =1 ;
6463else dp [M -1 ][j ] =dp [M -1 ][j +1 ] -dungeon [M -1 ][j ];
6564 }
6665for (int i =M -2 ;i >=0 ; --i ) {
6766for (int j =N -2 ;j >=0 ; --j ) {
6867int val =Math .min (dp [i +1 ][j ],dp [i ][j +1 ]);
69- if (dungeon [i ][j ] >val )dp [i ][j ] =1 ;
68+ if (dungeon [i ][j ] >= val )dp [i ][j ] =1 ;
7069else dp [i ][j ] =val -dungeon [i ][j ];
7170 }
7271 }
