动态规划 —— 路径问题-地下城游戏

1. 地下城游戏

题目链接：

174. 地下城游戏 - 力扣（LeetCode）https://leetcode.cn/problems/dungeon-game/description/

2.  算法原理 

状态表示：以莫一个位置位置为结尾或者以莫一个位置为起点

   

dp[i，j]表示：到达[i，j]位置的时候，骑士所需要的最低初始健康点数（X），这个状态表示是错误的，因为如果是以莫一个位置为结尾来推导的话我们会发现我们正向推导的时候是不断的修改我们之前的状态，无法得到一个准确的状态

  

所以本题应该以莫一个位置为起点来开始推断：从[i，j]位置出发，到达终点，dp[i，j]里面存储的值就是所需的最低初始健康点数

2. 状态转移方程

  

根据最近的一步来划分问题：

   

到达dp[i][j]有两种情况：

                                        1. 往右边走：dp[i，j+1] - d[i][j]

        

                                        2. 往下走：dp[i+1，j] - d[i][j]
    

    

本题的状态转移方程是：dp[i][j] = min(dp[i，j+1]  ,dp[i+1，j]) - d[i][j]

    

因为最低健康点数还有可能为负数，那么我们还需要对它进行一次比对：

   

                                dp[i][j] =max(1,dp[i][j] )        如果为负数则返回1，否则不变

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

    

本题状态依赖的是下面和右边的状态，所以会越界的位置是下面的一行和右边的一列，那么我们可以在下面的一行和右边的一列再额外的加上一行和一列的虚拟节点

   

因为是在下面的一行和右边的一列加上了虚拟节点，所以不用考虑下标的映射关系，只需要保证后面的填表是正确的

    

当解救完公主之后走到下面或者右边的时候，最少要剩下1滴健康点数，其余虚拟节点的值是取最小的值，为了防止影响到最终结果，所以我们将其初始化为正无穷大

   

4. 填表顺序 

    

本题的填表顺序是：从下往上填写每一行，每一行的值是从右往左

5. 返回值 ：题目要求 + 状态表示 

    

本题的返回值是：dp[0][0]

3.代码  

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值 

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

        //创建dp表随便将虚拟节点全部初始化为正无穷大
        vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));

        //再将dp[m][n-1]和dp[m-1][n]初始化为1
        dp[m][n-1]=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];
    }
};

感谢观看~