931. Minimum Falling Path Sum

Idea

這題偏簡單
目的是從 m * n 的二維陣列中找到 最小下落總和
下落的路徑只能有三種選擇(向左偏移、垂直向下、向右偏移)

我們定義一個 1 * n 的 dp 陣列
每個陣列點的意義代表著最後落在該點的最小下落總和
每次計算第 j 個落點之狀態都需要比較其前三個狀態 j - 1、j、j + 1

還要稍微留意兩件事

1. 邊界處理 - 在最左邊之點取向左偏移和最右邊之點取向右偏移會導致 取到 undefined 使 Math.min 計算爆炸算出 NaN，我們用 Infinity 迴避取不到陣列之值時所造成的計算錯誤。
2. 陣列備份 - 我們需要在每次計算一輪新的 dp 時先拷貝上一輪的 dp，才能確保狀態的計算不會受影響(廢話)。

時間複雜度為 O( m * n )
空間複雜度為 O( n )

function minFallingPathSum(matrix) {
  const m = matrix.length,
    n = matrix[0].length,
    dp = Array(n).fill(0)
  for (let i = 0; i < m; i++) {
    let prev = [...dp]
    for (let j = 0; j < n; j++) {
      dp[j] =
        Math.min(prev[j - 1] || Infinity, prev[j], prev[j + 1] || Infinity) +
        matrix[i][j]
    }
  }
  return Math.min(...dp)
}

Refactor

我覺得已經是 masterpiece 了
有更猛的解法拜託教一下

tags: Leetcode JavaScript