题目
思路分析
看到这道DP问题，第一反应就是跟 62.不同路径、63.不同路径Ⅱ 特像，然后根据之前的思路，直接声明一个dp数组，然后从头到尾更新dp数组取最低的初始健康点数似乎可行，但是因为在地图中既有扣血的恶魔也有加血的魔法球，因此要对加血后的血量状态值进行保存，所以还需要一个额外的helper数组来存储骑士当前的健康状态(即走过的路的路径和)。
然后就要考虑怎么进行状态转移了，如果片面的考虑题目给出的例子，最后期望的是得到最小的dp数组的值，所以优先考虑dp数组的值决定走哪一格，然后dp数组相等的情况再来判断helper数组的值似乎是合理的。于是就会得到如下的状态转移方程：
if (dp[i - 1][j] > dp[i][j - 1]) {
helper[i][j] = helper[i][j - 1] - dungeon[i][j];
dp[i][j] = Math.max(dp[i][j - 1], helper[i][j]);
} else if (dp[i - 1][j] == dp[i][j - 1]) {
helper[i][j] = Math.min(helper[i - 1][j], helper[i][j - 1]);
dp[i][j] = Math.max(helper[i][j],
(helper[i - 1][j] > helper[i][j - 1] ? dp[i][j - 1] : dp[i - 1][j]));
} else {
helper[i][j] = helper[i - 1][j] - dungeon[i][j];
dp[i][j] = Math.max(helper[i][j], dp[i - 1][j]);
}
但是，这样考虑其实是不正确的，因为官方给出的例子毕竟还是片面的，我们可以考虑如下的例子：
当计算到图中第一个问好位置时，dp[1][1] < dp[0][2]，而helper[1][1] > helper[0][2]，这时候如果按照上边的算法来选择路径会选择图中的绿色路径，得到答案
4，不过这样并不是最优解，应当走红色路径，得到答案 2。这是因为最后一个格子为 -3，如果最后一个格子为0，那么又应该走图中的绿色路线。通过这里可以发现上边的选路方法并不正确，另外，通过官方例子和上边的例子，dp[i][j]的大小和helper[i][j]的大小似乎都不能进行路径的选择，综合到一起也不能得出正确答案，因为具体的走那条路还和后边的格子有关，需要根据后边的格子进行选择，所以这样判断必然要考虑所有方案，也就是相当于进行递归遍历了，显然这种想法不能解决问题。
这道题我做到这里就想不出什么思路了，于是参考了题解，才得知像这样两个同等重要的参数同时影响后续决策的问题，不满足动态规划的[无后效性]，所以这样遍历是得不到绝对正确的答案的。正确的遍历方式应当是倒序遍历，从右下至左上进行遍历，而为什么这么遍历呢？评论区的Shine Hugh大佬给的解释十分清晰：
确实如他所说，直接使用不同问题的思路进行左上开始遍历并不是基于已知解的，在划分子问题的时候就已经错了，如果子问题划分为其所说的“从i, j到达终点需要的最小生命值”，这样很容易想到初始状态为从终点到终点需要的最小生命值，那么从右下到左上遍历也就显而易见了。
完整代码
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
if (dungeon == null)
return 0;
int n = dungeon.length;
if (n == 0)
return 0;
int m = dungeon[0].length;
int[][] dp = new int[n + 1][m + 1];// dp[i][j]表示走到i , j 格所需要的最低初始健康点数
for(int i = 0; i <= n; i++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
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--){
dp[i][j] = Math.max(Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1);
}
}
return dp[0][0];
}
}
这里还要注意出现某一个格子吃到魔法球使得所需生命值变为0，或者负数的情况，虽然变成负数，但是负数只对该格子后边的路径有影响，对前边没遍历到的格子没有影响，所以保证最低血量为1即可。
总结
之前也做了不少的DP问题了，但是做的都是正向遍历和反向遍历都可以的，还是第一次碰到这种考虑到后效性的问题，特此记录一下，方便以后复习查看。如果有写的不正确的地方还请指出。感恩相遇~
