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

1.题目解析

题目来源：174.地下城游戏 

测试用例 

2.算法原理

1.状态表示

通常dp[i,j]可以表示终点也可以表示起点，在本题中如果表示为终点，即勇士到[i,j]位置所需要的最小生命值，但是由于后续位置的未知无法向后继续判断，无解

所以在本题中将dp[i,j]表示为起点，即以[i,j]位置为起点到公主位置所需要的最小生命值，这样表示可以不被未知数据影响

2.状态转移方程

本题dp[i,j]表示以[i,j]位置为起点到公主所需要的最小生命值，所以可以列出下列表达式：dp[i][j]+d[i][j] >= min(dp[i+1][j],dp[i][j+1])，含义为勇士以[i,j]位置为起点并拾取该位置道具后的生命值一定大于等于下一个位置的生命值，否则就不能解救公主，下一个位置是消耗生命值较小可以到达的位置，所以对两个位置取Min值，由于取最小生命值，所以最终的状态转移方程就是：dp[i][j] = min(dp[i+1[j],dp[i][j+1]) - d[i][j]，由上面式子化简得到 

3.初始化

本题需要从后向前填表，所以初始化时的虚拟位置设置在最下面与最右面一行一列，并且需要取min因此在公主位置必须保证勇士至少有一滴血，则将该位置的下面与右边虚拟位置初始化为1，其他位置不能影响dp表真实数据，则设置为INT_MAX 

4.填表顺序

从下向上，每一行从右向左 

5.返回值

返回从左上角开始为起点救出公主需要的最小生命值，则直接返回dp表的第一个元素dp[0][0] 

3.实战代码 

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& d) {int m = d.size();int n = d[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--){//以[i,j]位置为起点到公主所在位置需要的生命值dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - d[i][j];//如果下个位置是个很大的雪豹，说明负血量也可以到下个位置，//但是显然不符合题目，所以将血量置为1初始值dp[i][j] = max(1,dp[i][j]);}}//返回以左上角为起点救出公主需要的生命值return dp[0][0];}
};