967.下降路径最小和 II

下降路径最小和 II

给定 n x n 整数矩阵，返回非零偏移下降路径的最小和。路径从第一行到最后一行，每次移动到下一行相邻列（对角线方向）。

示例 1:

输入：grid = [[2,1,3],[6,5,4],[7,8,9]]
输出：13

提示:

• n == grid.length == grid[i].length
• 1 <= n <= 200
• -99 <= grid[i][j] <= 99

解析

动态规划，对于每个位置，选择上一行中与当前列不同的最小值。

var minFallingPathSum = function (grid) {
  const n = grid.length;
  const dp = grid[0].slice();

  for (let i = 1; i < n; i++) {
    const next = [];
    for (let j = 0; j < n; j++) {
      let min = Infinity;
      for (let k = 0; k < n; k++) {
        if (k !== j) min = Math.min(min, dp[k]);
      }
      next.push(grid[i][j] + min);
    }
    dp.length = 0;
    dp.push(...next);
  }

  return Math.min(...dp);
};

时间复杂度 O(n^3)，空间复杂度 O(n)。可优化至 O(n^2)。