题目：
题解：
思路：还是使用三角形模型，不过需要从右下到左上进行 状态转移 即可。
代码如下：
class Solution {
public:
/*
思路：线性dp
如果按照之前的「62. 不同路径」从左上到右下的顺序进行动态规划的话，对于每一条路径，我们需要同时记录两个值，第一个值是
从【从出发点到当前点的路径和】，第二个值是【从出发点到当前点所需的最小初值】，而这两个值的重要程度相同。
我们应该让【从出发点到当前点的路径和】尽可能地大，而让【从出发点到当前点所需的最小初值】尽可能地小，而从左上到右下的状态转移，不满足动态规划的【无后效性】。因此考虑从右下到左上的动态规划。
f[i][j]表示从(i,j)这个点到终点所需的最小初值，此时只要我们的路径和大于等于f[i][j]就能走到终点，这样一来，我们就不需要关心路径和问题了，只需关心最小初值。
f[i][j]=min(f[i+1][j],f[i][j+1])-g[i][j] 从右边和正下方两个点进行转移；同时初始值必须大于等于1，因为任何时刻生命值必须大于0，所以上面那个转移方程还需要与1取一个max即可
*/
int calculateMinimumHP(vector<vector<int>>& g) {
int n=g.size(),m=g[0].size();
vector<vector<int>> f(n+1,vector<int>(m+1,INT_MAX));
// 边界条件：边界f[n-1][m-1]需要用到f[n][m-1]和f[n-1][m]，对于这两个值需要初始化为1，表示最小初值必须大于0
f[n][m-1]=f[n-1][m]=1;
// 开始从右下到左上进行状态转移
for(int i=n-1;i>=0;i--)
for(int j=m-1;j>=0;--j)
f[i][j]=max(min(f[i+1][j],f[i][j+1])-g[i][j],1);
return f[0][0];
}
};
