My understanding for this problem.


  • 0

    When starting from the top-left, you need to stand on this point, and look the point forward and downward. Then ask yourself a question: if I know the minimum healthy values of the two points, which direction should I go. Of course, the smaller one. Because if you chose the bigger one, you need more healthy value to spend. So the memorization code:

    class Solution {
    public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int r=dungeon.size();
        int c=dungeon[0].size();
        vector<vector<int>> d(r+1, vector<int>(c+1, INT_MIN));
        d[r][c-1]=1;
        build(dungeon, d, 0, 0);
        return d[0][0];
    }
    int build(vector<vector<int>>& dungeon, vector<vector<int>>& d, int i, int j){
        int& ans=d[i][j];
        if(ans!=INT_MIN){
            return ans;
        }
        else{
            if(i==d.size()-1) {
                ans=INT_MAX;
            }
            else if(j==d[0].size()-1) {
                ans=INT_MAX;
            }
            else{
                int f=build(dungeon, d, i+1, j); // forward point.
                int b=build(dungeon, d, i, j+1); // downward point.
                ans=max(1, min(f, b)-dungeon[i][j]); // should always be positive.
            }
            return ans;
        }
    }};
    

    But, as always, if it can be written in memorization, it should be able to be written in iterative way. Since we need to know forward and downward values, it forces us to start from the bottom-right. Again, when you stand on a point, look forward and downward, given the two healthy values, which one do you chose? The smaller one. Then how to make sure start from the current point, and move one step, you have the smaller healthy point left? You know that.

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

  • 0

    In the recursive solution, where do you set the d variables? I don't see anything.


  • 0

    @agave I set the value to the reference

    int& ans.
    

Log in to reply
 

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