逆向递归

  1. 这道题的 dp 是倒序的，这点很重要，为什么不能像【最小路径和】一样是正序的？因为【最小路径和】是无状态的，你会发现【最小路径和】倒序 dp 也是可以的，这道题由于有 “加血” 的过程，只能依赖后面的值判断需要的血量。所以这里的 dp [i][j] 表达的意思是：“从（i，j）出发，到达终点需要最少的血量”。因此，正序的含义为 “从起点出发，到达位置（i，j）所需要的最少血量”；倒序的含义是 “从（i，j）出发，到达终点需要最少的血量”。初始血量本来就是要求的，所以只能倒序 dp

地下城 - 图1

  1. var calculateMinimumHP = function (dungeon) {
  2.   let m = dungeon.length;
  3.   let n = dungeon[m - 1].length;
  4.   let dp = [];
  5.   for (let i = 0; i <= m; i++) {
  6.     dp[i] = new Array(n + 1).fill(Infinity);
  7.     //这里之所以m和n都要+1，是为了m-1>=0,n-1>=0; 动态规划系列解法都如此;
  8.   }
  9.   dp[m][n - 1] = dp[m - 1][n] = 1;//当到达p后，假设刚好剩下1滴血;
  10.   for (let i = m - 1; i >= 0; i--) {
  11.     for (let j = n - 1; j >= 0; j--) {
  12.       //因为只能向右或向下，所以求出向右或者向下时，消耗最低的那一步;
  13.       let minHp = Math.min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j]);
  14.       dp[i][j] = Math.max(minHp, 1);//dp[i][j]是我们到达此坐标，还剩多少血;
  15.     }
  16.   }
  17.   return dp[0][0];//出发时的最低血量
  18. };