931.下降路径最小和.md

931.下降路径最小和

/*
 * @lc app=leetcode.cn id=931 lang=typescript
 *
 * [931] 下降路径最小和
 */

// @lc code=start
function minFallingPathSum(matrix: number[][]): number {}
// @lc code=end

解法 1: 动态规划

• 动态规划:
  • dp[i]: 第 i 个元素的下降路径和
  • dp[i]=min(dp[i-1],dp[i],dp[i+1])+row[i]

function minFallingPathSum(matrix: number[][]): number {
  const n = matrix.length
  let [dp, pre, min] = [new Array(n).fill(0), 0, Infinity]
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const next = dp[j + 1] ?? Infinity

      // 计算当前位置的最小路径和,以及将上一行的当前位置路径和赋值给 pre
      // 分开写需要用另外一个变量去存,用解构赋值更简洁一些
      ;[dp[j], pre] = [Math.min(pre, dp[j], next) + matrix[i][j], dp[j]]

      // 到最后一行时,记录最小值,用以返回答案
      if (i === n - 1) min = Math.min(min, dp[j])
    }
    pre = Infinity
  }

  return min
}

Case

test.each([
  {
    input: {
      matrix: [
        [2, 1, 3],
        [6, 5, 4],
        [7, 8, 9],
      ],
    },
    output: 13,
  },
  {
    input: {
      matrix: [
        [-19, 57],
        [-40, -5],
      ],
    },
    output: -59,
  },
  { input: { matrix: [[-48]] }, output: -48 },
])('input: matrix = $input.matrix', ({ input: { matrix }, output }) => {
  expect(minFallingPathSum(matrix)).toBe(output)
})