C++ DP solution


  • 108
    S

    Use hp[i][j] to store the min hp needed at position (i, j), then do the calculation from right-bottom to left-up.

    Note: adding dummy row and column would make the code cleaner.

    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int> > &dungeon) {
            int M = dungeon.size();
            int N = dungeon[0].size();
            // hp[i][j] represents the min hp needed at position (i, j)
            // Add dummy row and column at bottom and right side
            vector<vector<int> > hp(M + 1, vector<int>(N + 1, INT_MAX));
            hp[M][N - 1] = 1;
            hp[M - 1][N] = 1;
            for (int i = M - 1; i >= 0; i--) {
                for (int j = N - 1; j >= 0; j--) {
                    int need = min(hp[i + 1][j], hp[i][j + 1]) - dungeon[i][j];
                    hp[i][j] = need <= 0 ? 1 : need;
                }
            }
            return hp[0][0];
        }
    };

  • 9
    H

    we can use the original dungeno for DP data storage.
    Use O(mn) time, O(1) memory.

     class Solution {
        public:
          int calculateMinimumHP(vector<vector<int> > &dungeon) {
            int m = dungeon.size(), n = dungeon[0].size();
            dungeon[m - 1][n - 1] = dungeon[m - 1][n - 1] > 0 ? 1 : abs(dungeon[m - 1][n - 1]) + 1;
            for (int i = n-2; i >= 0; --i)
              dungeon[m - 1][i] = max(dungeon[m - 1][i + 1] - dungeon[m - 1][i],1);
            for (int i = m - 2; i >= 0; --i)
              dungeon[i][n - 1] = max(dungeon[i + 1][n - 1] - dungeon[i][n - 1],1);
            for (int i = m-2; i >= 0;--i)
              for (int j = n-2; j >= 0; --j)
                dungeon[i][j] = max(min(dungeon[i + 1][j], dungeon[i][j + 1]) - dungeon[i][j],1);
            return dungeon[0][0];
          }
     };

  • 0
    S

    add dummy row and column is quite easier to understand the code!


  • 18
    I

    We could reduce the 2-D DP matrix into 1-D

    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            int n=dungeon.size(),m=dungeon[0].size();
            vector<int> dp(n+1,INT_MAX);
            dp[n-1]=1;
            for(int j=m-1;j>=0;j--){
                for(int i=n-1;i>=0;i--){
                    dp[i]=min(dp[i],dp[i+1])-dungeon[i][j];
                    dp[i]=max(1,dp[i]);
                }
            }
            return dp[0];
        }
    };

  • 1

    Great code, though I wonder whether it would be better the keep the input unmodified if the function has a return value. Anyway, your code is good :-)


  • 0

    Great optimization! I think it will be easier for other people to understand your code after they become clear of the updating process of the above 2d code. Thanks for your sharing :-)


  • 0
    Y

    Could you please explain this line: hp[i][j] = need <= 0 ? 1 : need;


  • 2
    J

    @youranjoy: the idea is that at the slots where the knight is gaining health the "need" for the knight to carry more health from the start point reduces. The knight should arrive with the bare minimum health at these points, i.e, 1. And due to the previous line if the knight gains health at any slot the need will be reduced. So if the knight gains too much health, it will be reduced to 1.


  • 2
    M

    Why do we start from the bottom right corner? Couldn't we start at the top left corner too?


  • 5
    J

    Because it is known that the knight has to reach the end with at least one health point and the health point with which the knight should start with is not known.


  • 0
    M

    Thanks, I got it!


  • 0
    M

    I wonder INT_MAX-dungeon[i][j] would be overflow if dungeon[i][j] is negative.


  • 0
    O

    @huoyao reusing the input array doesn't mean it an O(1) space.


  • 0

    i don't think it is a right solution.

    first, it returns 6 instead of 7 ( the right answer)

    second, if we change P from -5 to -50, the results is still 6.


  • 0

    The reason to start from bottom right to top left is that the magic orbs closing to the princess could be used to compensate those hp cost on path.


  • 0
    B

    Why this answer is correct? the author only assign value to hp[m][n-1] and hp[m-1][n], but not considering other value in the dummy row and dummy column. Anybody can help make it more detailed?


  • 0
    S

    @bd117 All the other values were initialized to INT_MAX.


  • 0
    B

    @sidbai sorry I just see it.


  • 0
    T

    This solution assumed that the knight can only move right or down. However, there is no constraint, so why this assumption holds?


  • 0

    @SaltedFish I'm not able to figure out how can this not be achieved when we start from top left? In OP's solution dp[i][j] means the minimum hp knight needs at i j position to reach princess. If we start from top left, dp[i][j] would be defined as the minimum hp needed to reach point i j from top left corner and we finally return dp[m][n], why can't this work?


Log in to reply
 

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