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

• 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.

• This post is deleted!

• Could you give some explanation for it? Thanks

• 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].

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

• yes, it could be more simple

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