2022-12-13.md

题目

931. Minimum Falling Path Sum

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

思路

代码

var minFallingPathSum = function(matrix) {
  let sum = Array.from(matrix[0])
  for (let row = 1; row < matrix.length; row++) {
    const nextSum = []
    for (let col = 0; col < matrix[0].length; col++) {
      const start = Math.max(0, col - 1)
      const end = Math.min(matrix[0].length, col + 2)
      nextSum[col] = matrix[row][col] + Math.min(...(sum.slice(start, end)))
    }
    sum = nextSum
  }
  return Math.min(...sum)
}