Who can explain why “from the bottom right corner to left top.”

It depends on the way you formulate the problem. If you define a value in DP table d[i][j] as 'the minimum hp required to REACH (i, j) from (0, 0)", then the final answer should be d[n_rows1][n_cols1], and you need to start filling from the top left; However, in the reference answer provided with the question, dp[i][j] is defined as 'the minimum hp required to REACH (n_rows1, n_cols1) from (i, j)'. Here dp[0][0] is the final answer so we must fill from (n_rows1, n_cols1). For many other problems such as 'Minimum Path Sum', both formulation would work. However, in this problem, the former formulation will lead us to trouble, because it is very hard, if not impossible, to get d[i][j] based on d[i1][j] and d[i][j1].

If we start from left top, in addition to minimize initial HP required to get
(i,j)
, we also have to maximize HP left when we get(i,j)
in order to decide whether we need more initial HP in the next step. It doesn't directly depend on things at(i1,j)
and(i,j1)
.For example, at some point we have two paths, from left or from up.
 Left: min HP required is 1, max HP left is 1
 Up: min HP required is 5, max HP left is 100
How do we choose now? If we choose smaller min HP required, this requirement may increase to 5 later anyway and 95 HP is wasted.
I'd be happy to know if anyone can do this from lefttop (not trying different initial HP values).

This is because, in order to compute HP[i][j], you will need to make sure of two things:
 your HP[i][j]+dungeon[i][j] should be >0
 your HP[i][j]+dungeon[i][j] should be large enough, so that it will be sufficient to cover the minimum requirement on HP for the next step, be it right or down (take whichever requires smaller HP).
So you see, because of the second requirement, your calculation of HP[i][j] will depend on later steps that you could take. This is why you have to know these later steps ahead of time, thus calculating from the bottom right.

I actually fill the tables from left top to right corner. The drawback is more space used.
Two arrays are used: one for saving minimum cost, one for saving minimum knight HP.public class Solution { public int calculateMinimumHP(int[][] dungeon) { int width = dungeon.length; int height = dungeon[0].length; int minCostArray[][] = new int[width][height]; int minKnightBlood[][] = new int[width][height]; for (int i = 0; i < width; i++) { for (int j = 0; j< height; j++) { if (i == 0 && j == 0) { minCostArray[i][j] = dungeon[i][j]; minKnightBlood[i][j] = Math.max(1  minCostArray[i][j], 1); } else if (i == 0) { minCostArray[i][j] = minCostArray[i][j  1] + dungeon[i][j]; minKnightBlood[i][j] = Math.max(minKnightBlood[i][j  1], 1  minCostArray[i][j]); } else if (j == 0) { minCostArray[i][j] = minCostArray[i  1][j] + dungeon[i][j]; minKnightBlood[i][j] = Math.max(minKnightBlood[i  1][j], 1  minCostArray[i][j]); } else { minCostArray[i][j] = Math.max(minCostArray[i  1][j], minCostArray[i][j  1]) + dungeon[i][j]; minKnightBlood[i][j] = Math.min( Math.max(minKnightBlood[i  1][j], 1  minCostArray[i  1][j]  dungeon[i][j]), Math.max(minKnightBlood[i][j  1], 1  minCostArray[i][j  1]  dungeon[i][j]) ); } } } return minKnightBlood[width  1][height  1]; } }