// 由下至上找出每个步骤离终点的最佳距离
var minPathSum = function(grid) {
  const m = grid.length, // 二维长度
    n = grid[0].length; // 二维宽度
  // 倒序遍历
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      // 计算每一步移动到终点位置的代价 得到最终代价
      if (i + 1 < m && j + 1 < n) {
        // 可以向左和向上移动的情况 取最小值 动规
        grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]);
      } else if (i + 1 < m) {
        // 只能向上移动的情况
        // 加上下一行数组的最后一个元素 计算向上移动的代价
        grid[i][j] += grid[i + 1][j];
      } else if (j + 1 < n) {
        // 只能向左移动的情况
        // 加上右侧的原先的值 计算向左移动的代价
        grid[i][j] += grid[i][j + 1];
      }
    }
  }
  console.log("grid", grid);
  return grid[0][0]; // 由起点到终点的位置
};

var minPathSum = function(grid) {
  const m = grid.length, // 二维长度
    n = grid[0].length; // 二维宽度
  const memo = [...Array(m)].map(() => [...Array(n)]); // 初始化二维数组
  const calcPath = function(i, j) {
    if (i + 1 === m && j + 1 === n) {
      return grid[i][j]; // 返回终点位置的值
    }
    if (memo[i][j]) {
      return memo[i][j]; // 计算过了, 不重复计算
    }
    let min = Infinity; // 初始化最大值
    // 计算往右走以及往下走的步数，取最小值
    if (i + 1 < m) {
      // 防止右侧出界
      // 计算往右走的最终代价
      min = Math.min(min, calcPath(i + 1, j));
    }
    // 往下走的步数
    if (j + 1 < n) {
      // 防止下方出界
      // 计算往下走的最终代价
      min = Math.min(min, calcPath(i, j + 1));
    }
    memo[i][j] = min + grid[i][j]; // 终点到当前位置的代价
    return memo[i][j]; // 返回每个位置到终点位置的代价
  };
  let res = calcPath(0, 0);
  return res;
};