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.

Capture

Notes:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

这题目看着挺花哨的,其实和64. Minimum Path Sum是一样的。我们仍然开一个DP[j]数组(为什么只开一维数组的解释在64题题解里),不同的是虽然knight的顺序是从左上到右下,但求的却是起始最小血量,所以我们需要反过来逆推出这个血量,也就是说我们要从右下出发回到左上,求出这个过程中到达左上角时候的最小值。这个过程需要注意两点:

  1. 由于是逆推,所以方向是只能向左和向上,而且每步要减去该格的value,如起始状态就是 1 – (-5) = 6,意思就是到达最后一格前至少要有6的血量。
  2. 当减去该格value小于1的时候说明即使只有最少的1点血都可以在该格存活,直接把该格DP值设为1即可。

其它的部分和64题几乎一样,最后返回DP[j – 1]。

Solution:


class Solution {
public:
        int DP[1000];
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
                if(dungeon.size() == 0) return 1;
                if(dungeon[0].size() == 0) return 1;
                int n = dungeon.size();
                int m = dungeon[0].size();
        
                DP[m - 1] = 1;
                for(int i = n - 1; i >= 0; --i)
                {
                        for(int j = m - 1; j >= 0; --j)
                        {
                                if(j != m - 1)
                                {
                                        if(i == n - 1) DP[j] = DP[j + 1];
                                        else DP[j] = min(DP[j + 1], DP[j]);
                                }
                                DP[j] -= dungeon[i][j];
                                if(DP[j] <= 0) DP[j] = 1;
                        }
                }
                return DP[0];
        }
};

Leave a Reply

Your email address will not be published. Required fields are marked *