DP学习第八篇之地下城游戏

DP学习第八篇之最小路径和

174. 地下城游戏 - 力扣（LeetCode）

一.题目解析

按照红色路线前进，要保证在经过每一步后血量>0，最低值为7

二. 算法原理

1. 状态表示

    tips: 经验+题目要求。

• 以[i,j]位置为结尾，。。。

dp[i][j]: 到达[i, j]位置时，初始所需最低健康点数

由上文题目分析，可以发现：健康值会受到后续关卡的影响。即：只用前面的状态不能正确的推导出起始所需的最低健康点数(无法推导状态转移方程)，因此这种状态表示是错误的，有后效性的

• 以[i,j]位置为起点，。。。

dp[i][j]: 从[i, j]出发，到达终点，所需最低健康点数

2. 状态转移方程

    tips: 用之前或之后的状态，推导出dp[i]的值。根据最近的一步，来划分问题

从[i, j]位置出发，最近一步：

• 向右走一步，到达[i, j + 1]位置

• 向下走一步，到达[i + 1, j]位置

dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - d[i][j]、dp[i][j] = max(1, dp[i][j])

3. 初始化

    tips: 保证填表的时候不越界。增加虚拟节点

• 虚拟节点里面的值，要保证后面填表是正确的

根据状态转移方程，要保证填表时的正确性，对虚拟节点进行赋值

• 下标的映射关系

dp表映射到原矩阵：对应位置映射

4. 填表顺序

从下往上填写每一行，每一行从右往左

5. 返回值

题目要求：从左上角出发，骑士的最低初始血量

即：return dp[0][0]

三. 编写代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& d) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        int m = d.size(), n = d[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

        dp[m - 1][n] = 1;

        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]) - d[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }

        return dp[0][0];
    }
};

    🦀🦀观看~~