# 931. Minimum Falling Path Sum


### Idea

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

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

還要稍微留意兩件事

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

時間複雜度為 O( m \* n )<br />
空間複雜度為 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 了<br />
有更猛的解法拜託教一下

###### tags: `Leetcode` `JavaScript`