Minimum Falling Path Sum

Description

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one.

 

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:

• [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
• [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
• [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.

 

Constraints:

• 1 <= A.length == A[0].length <= 100
• -100 <= A[i][j] <= 100

Solution(javascript)

/*
 * @lc app=leetcode id=931 lang=javascript
 *
 * [931] Minimum Falling Path Sum
 */

// @lc code=start
// /** 1: Top-down Approach
//  * @param {number[][]} A
//  * @return {number}
//  */
// const minFallingPathSum = function (A) {
//   const memo = {}
//   const aux = (row, column) => {
//     const key = `${row}_${column}`
//     if (memo[key] !== undefined) {
//       return memo[key]
//     }
//     if (row > A.length - 1) {
//       return 0
//     }
//     if (column < 0 || column > A[row].length - 1) {
//       return Infinity
//     }
//     memo[key] = A[row][column] + Math.min(
//       aux(row + 1, column + 1),
//       aux(row + 1, column),
//       aux(row + 1, column - 1),
//     )
//     return memo[key]
//   }
//   let min = Infinity
//   for (let column = 0; column < A[0].length; column++) {
//     min = Math.min(
//       min,
//       aux(0, column),
//     )
//   }
//   return min
// }

/** 1: Top-down Approach
 * @param {number[][]} A
 * @return {number}
 */
const minFallingPathSum = function (A) {
  let memo = A[A.length - 1]
  for (let row = A.length - 2; row >= 0; row--) {
    const current = []
    for (let column = 0; column < A[row].length; column++) {
      current[column] = A[row][column] + Math.min(
        memo[column],
        memo[column - 1] || Infinity,
        memo[column + 1] || Infinity,
      )
    }
    memo = current
  }
  return Math.min(...memo)
}
// @lc code=end