leetcode--174--地下城游戏

题目：
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)  -3  3
-5  -10 1
10  30  -5 (P)

说明:

骑士的健康点数没有上限。

任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

链接：https://leetcode-cn.com/problems/dungeon-game

思路：
1、这道题可以用动态规划来解决，不过特殊点在于由于骑士体力值只要不大于0就会死亡，所以如果按照正常的顺序从左上到右下找的话是走不通的，因为缺少了后验信息，并不知道从那条路走需要体力值最少
2、这个题可以从右下往左上走，这样可以确保每次走的路是需要体力值最少的路
3、代码中max函数里面1的主要目的是确保勇士的体力值大于0

C++代码：

#include<algorithm>
#include<cstdio>
#include<cmath>

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0)); 

        for (int i=m-1; i>=0; i--){
            for (int j=n-1; j>=0; j--){
                if (i==m-1 && j==n-1){
                    dp[i][j] = max(1, 1-dungeon[i][j]);
                }else if (i==m-1){
                    dp[i][j] = max(1, dp[i][j+1]-dungeon[i][j]);
                }else if (j==n-1){
                    dp[i][j] = max(1, dp[i+1][j]-dungeon[i][j]);
                }else{
                    dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1])-dungeon[i][j]);
                }
            }
        }
        return dp[0][0];
    }
};