本文主要是介绍动态规划——达拉崩吧，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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]的计算
dp[m][n - 1] = dp[m - 1][n] = 1;
在dp表最后⾯添加⼀⾏，并且添加⼀列后，所有的值都先初始化为⽆穷⼤，然后让
dp[m][n - 1] = dp[m - 1][n] = 1即可。
这篇关于动态规划——达拉崩吧的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
