本文主要是介绍leetcode 174.地下城游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：dp。
原先的时候其实是想这样用dfs的做法进行解答的，但是呢，是不对的。
这里作者dfs的思路是：首先找出来最小路径和，然后再处理最小路径和这条路径里面的初始值。但是，后来发现这样不一定是最优解，因为当我们的路径和并不是最小值的时候，也可能得到最小的初始值。官方案例上应该已经给出来实例了。
从左上到右下，dp[i][j]的意思就是：从起点到(i,j)的最小初始值多少。这样的话我们需要考虑两个问题：1.我们现在走的路径和是多少，是不是最优解？2.我们现在走到的这条路径和是不是最小初始值？这样的话我们需要考虑这种两个值，递推的不现实，上面也说了，如果顾及到前者，后者不一定是最优。所以我们需要换一种思路。
如果说我们正向推导不行，那么我们或许可以试一试反向推导。也就是说，我们从右下向左上进行推导。这给我们提供一种思路，就是正向推导行不通的时候我们可以试一试反向推导。
反向推的话，我们的dp就变成了：从(i,j)到终点的最低初始值。这样的话，我们就不需要顾及到路径和的问题了。因为我们现在已经在(i,j)这个坐标里面了，那么前面的路径和一定是不小于当前的最低初始值的，也就是说我们已经定下来了路径和一定是合理的，所以我们就相当于只考虑最低初始值的问题了。那么我们就只推它了。
我们也知道，我们站在这个位置有两条路可以选：一个就是向下走，一个就是向右走。那么我们需要知道，这两个路我们需要走哪个？当然是选择其中小的一个，因为我们求的是最低初始值。这样的话，我们需要初始化dp，这样的话，我们就需要为dp数组赋值一个很大的值以至于我们可以取到最小值。
那么，状态方程就出来了：dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])-dungeon[i][j])。看右边这子，为什么需要-dungeon[i][j]？由于我们还并没有走到下一步，并且还需要考虑到当前的值。
另外，为什么要和1作比较呢？我们从题目中可以知道，骑士的初始值并不能<=0。所以我们的初始值最低是1，所以如果右边这个式子<=0，那么我们就自动给它赋值成1.
上代码：
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int n=dungeon.size();int m=dungeon[0].size();vector<vector<int>>dp(n+1,vector<int>(m+1,INT_MAX));dp[n-1][m]=dp[n][m-1]=1;for(int i=n-1;i>=0;i--){for(int j=m-1;j>=0;j--){int mins=min(dp[i+1][j],dp[i][j+1]);dp[i][j]=max(1,mins-dungeon[i][j]);}}return dp[0][0];}
};这篇关于leetcode 174.地下城游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
