Minimum Falling Path Sum II

Description

Given a square grid of integers arr, a falling path with non-zero shifts is a choice of exactly one element from each row of arr, such that no two elements chosen in adjacent rows are in the same column.

Return the minimum sum of a falling path with non-zero shifts.

 

Example 1:

Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

 

Constraints:

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

Solution(javascript)

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

// @lc code=start
// /** 1: Top-down
//  * @param {number[][]} arr
//  * @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
//     }
//     let min = Infinity
//     for (let i = 0; i < A[0].length; i++) {
//       if (i !== column) {
//         min = Math.min(
//           min,
//           aux(row + 1, i),
//         )
//       }
//     }
//     memo[key] = A[row][column] + min
//     return memo[key]
//   }
//   let min = Infinity
//   for (let column = 0; column < A[0].length; column++) {
//     min = Math.min(
//       min,
//       aux(0, column),
//     )
//   }
//   return min
// }


// /** 2: Bottom-up Approach O(mn^2)
//  * @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++) {
//       let min = Infinity
//       for (let i = 0; i < A[0].length; i++) {
//         if (i !== column) {
//           min = Math.min(
//             min,
//             memo[i],
//           )
//         }
//       }
//       current[column] = A[row][column] + min
//     }
//     memo = current
//   }
//   return Math.min(...memo)
// }


/** 3: Bottom-up Approach O(mn^2)
 * 保存最小的两个值
 * 类似 paint house II
 * @param {number[][]} A
 * @return {number}
 */
const minFallingPathSum = function (A) {
  let min1 = [0, null] // [value, column]
  let min2 = [0, null]
  for (let row = A.length - 1; row >= 0; row--) {
    let current1 = null
    let current2 = null
    for (let column = 0; column < A[row].length; column++) {
      let currentSum = A[row][column]
      if (column !== min1[1]) {
        currentSum += min1[0]
      } else {
        currentSum += min2[0]
      }
      if (current1 === null || currentSum < current1[0]) {
        current2 = current1
        current1 = [currentSum, column]
      } else if (current2 === null || currentSum < current2[0]) {
        current2 = [currentSum, column]
      }
    }
    min1 = current1
    min2 = current2
  }
  return min1[0]
}
// @lc code=end