A clear C++ DP solution easy to understanding


  • 3
    R

    The basic idea is to solve it backward from the last node. we start from the last row, and use a vector to record the minimum hp requirements for each position if you want to reach the final point.

     int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size();
        if (n == 0) return -1;
        int m = dungeon[0].size();
        vector<int> cur(m);
        cur[m-1] = max(1, 1 - dungeon.back().back());
        //dealing with the last row
        for (int i = m - 2; i >= 0; --i) {
            cur[i] = max(1, cur[i+1] - dungeon.back()[i]);
        }
        for (int i = n - 2; i >= 0; --i) {
            //dealing with the last element of each row
            cur[m-1] = max(1, cur[m-1] - dungeon[i].back());
            for (int j = m - 2; j >= 0; --j) {
                cur[j] = max(1, min(cur[j], cur[j+1]) - dungeon[i][j]);
            }
        }
        return cur[0];
    }

  • 0
    H

    I'm impressed that you're using only O(n) space here. Great job.


  • 0
    R

    My suggestion is, for such problem, you always start from the m*n solution, after you have that, then optimize it by changing the code (or the pseudo code). It's easy to make mistake to start from the O(n) solution


Log in to reply
 

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