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


  • 8
    H

    Why we fill the table from the bottom right corner to left top?


  • 8
    S

    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_rows-1][n_cols-1], 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_rows-1, n_cols-1) from (i, j)'. Here dp[0][0] is the final answer so we must fill from (n_rows-1, n_cols-1). 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[i-1][j] and d[i][j-1].


  • 1

    What kind of trouble would you get if we start from top left?


  • 28
    K

    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 (i-1,j) and (i,j-1).

    For example, at some point we have two paths, from left or from up.

    1. Left: min HP required is 1, max HP left is 1
    2. 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 left-top (not trying different initial HP values).


  • 0
    R

    Thanks for your hint ! It really helps me out !


  • 16
    C

    This is because, in order to compute HP[i][j], you will need to make sure of two things:

    1. your HP[i][j]+dungeon[i][j] should be >0
    2. 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.


  • 6
    D

    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];
        }
    }

  • 1
    X

    Can you please explain why this works? That is, why does the following hold?

    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]));


  • 0
    O

    This can't be ac by OJ?


  • 2
    A

    This is not correct for case: [[1,-4,5,-99],[2,-2,-2,-1]]


  • 0
    W

    @kongweihan

    This is exactly the problem I encountered when I was trying to start from top left.
    But how should we decide the direction of dp based on different scenarios?


  • 1
    V

    @ZarickZheng

    Try the following example from top left

    [[0,0,0],[-1,0,0],[2,0,-2]]
    

    You would get wrong answer at the end. I have done a top-down approach and struggled with this test case


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.