【Leetcode】174. Dungeon Game（反向DP）

秒速五厘米 2022-02-02 11:39 186阅读 0赞

The demons had captured the princess (**P**) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (**K**) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (*negative* integers) upon entering these rooms; other rooms are either empty (*0's*) or contain magic orbs that increase the knight's health (*positive*integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

**Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.**

For example, given the dungeon below, the initial health of the knight must be at least **7** if he follows the optimal path `RIGHT-> RIGHT -> DOWN -> DOWN`.

题目大意：

给出地图，我们需要从左上角前往左下角，并且只能向下走或者向右走。其中整数代表我们增加的血量，负数表示扣除的血量，如果在某一格子中血量小于等于0则无法通过，包括最后一格。那么最小的初始血量是多少？

解题思路：

从题目中只允许向下走或者向右走可以看出DP。

那么如何DP，正向DP我们无法得知之后是否还会出现满足条件的值。

所以我们需要从终点开始反向DP。

那么终点需要保持血量至少为1，如何表示?

在原始数组中加入一行一列，最后一个位置的左边和下边分别为1，其余为INT\_MAX。

DP规则：

int hp = min(dungeon[i+1][j], dungeon[i][j+1]) - dungeon[i][j];
    dungeon[i][j] = hp<=0 ? 1:hp;

求出最小值减去本位置，若为负数表示多余的血量，若为正数表示需要的血量；所以负数的情况可以直接置为1即可。

class Solution {  
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            int m = dungeon.size();
            if(m==0) return 1;
            int n = dungeon[0].size();
            if(n==0) return 1;
            for(int i=0;i<m-1;i++)
                dungeon[i].push_back(INT_MAX);
            dungeon.back().push_back(1);
            dungeon.push_back(vector<int>(n-1, INT_MAX));
            dungeon.back().push_back(1);
            for(int i=m-1;i>=0;i--){
                for(int j=n-1;j>=0;j--){
                    int hp = min(dungeon[i+1][j], dungeon[i][j+1]) - dungeon[i][j];
                    dungeon[i][j] = hp<=0 ? 1:hp;   
                }
            }
            return dungeon[0][0];
        }
    };