动态规划10：174. 地下城游戏

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：174. 地下城游戏 - 力扣（LeetCode）

题解：

本题使用从起点开始到达dp[i][j]位置的方法行不通，因为dp[i][j]不仅被前面的位置影响，还会被后面位置影响

所以本题使用从dp[i][j]位置开始到达终点的方法

1.状态表示：dp[i][j]表示从dungeon[i][j]位置出发到达终点所需最低初始健康点数

2.状态转移方程：dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]; if(dp[i][j]<=0) dp[i][j]=1

3.初始化：在右下角多开一行一列，初始化和填表合并（多开位置需要填值：[m][n-1]和[m-1][n]位置填1，其余位置为正无穷）

4.填表顺序：从右下角往左上角填写

5.返回值：dp[0][0]

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {//状态表示//dp[i][j]表示从dungeon[i][j]位置出发到达终点所需最低初始健康点数//状态转移方程//dp[i][j]=min(dp[i+1][j]-dungeon[i][j],dp[i][j+1]-dungeon[i][j])//if(dp[i][j]<=0) dp[i][j]=1//创建dp表size_t m=dungeon.size();size_t 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;//填表（从右下角到左上角）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];if(dp[i][j]<=0) dp[i][j]=1;//最低健康值不可能为负数或0，最低为1}}return dp[0][0];}
};

这是使用从起点开始到达dp[i][j]位置的方法，此代码不行

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {//dp[i][j]表示到达dungeon[i][j]所需的最低初始健康点数//if(dungeon[i][j]<0)//dp[i][j]=min(dp[i-1][j]-dungeon[i][j],dp[i][j-1]-dungeon[i][j])//创建dp表size_t m=dungeon.size();size_t n=dungeon[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));//多开一行一列dp[0][1]=dp[1][0]=1;//填表for(int i=1;i<m+1;++i){for(int j=1;j<n+1;++j){if(dungeon[i-1][j-1]<0)dp[i][j]=min(dp[i-1][j]-dungeon[i-1][j-1],dp[i][j-1]-dungeon[i-1][j-1]);elsedp[i][j]=min(dp[i-1][j],dp[i][j-1]);}}return dp[m][n];}
};