动态规划——达拉崩吧

1、题目链接

174. 地下城游戏

2、题目分析

假如说我们正向推状态转移方程，很难推出来，因为这道题有“加血”的说法，只能依靠后面的值判断前面所需要的血量，也就是说，如果正向的dp表示从起点出发，到达（i，j）需要最少的血量，那么[i][j+1]也会影响dp[i][j]的值，所以不建议正向dp的做法，

dp[i][j]表示从[i][j]位置到终点的所需要的最低健康值，

假设dp[i][j]所需的最低健康值是x，那么他满足

x+dungeon[i][j]>=dp[i+1][j]或者

x+dungeon[i][j]>=dp[i][j+1]

那么状态转移方程就是 dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]

但是当前的位置dungeon[i][j]是一个比较大的正数时，dp[i][j]的值可能会变为0或者负数，但是我们要求dp[i][j]最小为1，所以我们可以这样写：

dp[i][j] = max(1, dp[i][j])

状态转移方程出来了，剩下的就简单了

倒序dp：

3、代码实现

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        // dp[i][j]表示从当前位置出发到达终点时所需的最低健康数
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        return dp[0][0];
    }
};

注意我们的dp数组，要多开一行和一列，并初始化，方便我们dp[i][j]的计算