Sharing my solution with O(n) space, O(mn) runtime


  • 25
    F

    Here is my solution using dp and rolling array --Dungeon Game:

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

    Note: Update from right to left and from bottom up.


  • 0
    P
    This post is deleted!

  • 0
    N

    Could you give some explanation for it? Thanks


  • 1
    F

    I just used rolling array to lower the space cost. Otherwise we can use dp[m][n] to update from right to left and from bottom up, like: dp[i][j] = getMin(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]); Then the answer shouble be dp[0][0].


  • 0
    M

    Nice, but it could be
    dp[j] = max(1, (min(dp[j], dp[j + 1]) - dungeon[i][j]));
    No need for getMin()


  • 0
    F

    yes, it could be more simple


Log in to reply
 

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