6 lines, 16 ms, C++, O(mn) Time, O(n) Space,


  • 18
    F
    struct Solution {
        int calculateMinimumHP(vector<vector<int>>& d) {
            vector<int> dp(d.size() + 1, INT_MAX);
            dp[d.size() - 1] = 1;
            for (int i = d[0].size() - 1; i >= 0; --i)
                for (int j = d.size() - 1; j >= 0; --j)
                    dp[j] = max(1, min(dp[j + 1], dp[j]) - d[j][i]);
            return dp[0];
        }
    };

  • 0
    O

    Great solution!
    I solved this problem with binary search, but it's too slow.


  • 0
    M

    why do you want to assign 1 when you get a negative value..?


  • 0
    S

    If at any point the health is <= 0, the soldier dies. So, the minimum possible value for minimum health at any given position is 1. Thus, when we get a negative value for the minimum health at a grid position, we just assign it 1.


  • 0
    K

    Alternatively last row first, bottom up

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

Log in to reply
 

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