931.Minimum Falling Path Sum
===

###### tags: `Medium`,`Array`,`DP`,`Matrix`

[931. Minimum Falling Path Sum](https://leetcode.com/problems/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)`.

### 範例

**Example 1:**


Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

**Example 2:**


Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

**Constraints**:

* n == `matrix.length` == `matrix[i].length`
* 1 <= `n` <= 100
* -100 <= `matrix[i][j]` <= 100

### 解答
#### Javascript

function minFallingPathSum(matrix) {
  if (matrix.length === 1) return matrix[0][0];
  const isInBound = (i, j) => i >= 0 && i < matrix.length && j >= 0 && j < matrix.length;
  for (let i = 1; i < matrix.length; i++) {
    for (let j = 0; j < matrix.length; j++) {
      const left = isInBound(i - 1, j - 1) ? matrix[i - 1][j - 1] : Infinity;
      const right = isInBound(i - 1, j + 1) ? matrix[i - 1][j + 1] : Infinity;
      const middle = matrix[i - 1][j];
      matrix[i][j] += Math.min(left, right, middle);
    }
  }

  return Math.min(...matrix[matrix.length - 1]);
}

> [name=Marsgoat][time= Dec 13, 2022]

#### C++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int target = matrix[i+1][j];
                if (j > 0) target = min(target, matrix[i+1][j-1]);
                if (j < n-1) target = min(target, matrix[i+1][j+1]);
                matrix[i][j] += target;
            }
        }
        int ans = INT_MAX;
        for (int j = 0; j < n; j++) {
            ans = min(ans, matrix[0][j]);
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Tue, Dec 13, 2022]

#### Python

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        for i in range(1, n):
            for j in range(n):
                matrix[i][j] += min(matrix[i-1][max(0, j-1):min(j+2, n)])
        return min(matrix[-1])

> [name=Yen-Chi Chen][time=Tue, Dec 13, 2022]

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        if n == 1: return matrix[0][0]

        def is_in_matrix(i, j, n):
            return 0 <= i < n and 0 <= j < n

        for i in range(1, n):
            for j in range(n):
                left, middle, right = math.inf, math.inf, math.inf
                if is_in_matrix(i-1, j-1, n):
                    left = matrix[i-1][j-1]
                if is_in_matrix(i-1, j, n):
                    middle = matrix[i-1][j]
                if is_in_matrix(i-1, j+1, n):
                    right = matrix[i-1][j+1]

                matrix[i][j] += min(left, middle, right)

        return min(matrix[n-1])

> General Solution
> [name=Kobe][time=Tue, Dec 13, 2022]

#### C#

public class Solution {
    public int MinFallingPathSum(int[][] matrix) {
        int len = matrix.Length;
        
        foreach (int row in Enumerable.Range(1, len - 1)) {
            foreach (int col in Enumerable.Range(0, len)) {
                var colRange = Math.Max(0, col - 1)..Math.Min(len, col + 2);
                matrix[row][col] += matrix[row - 1][colRange].Min();
            }
        }

        return matrix[^1].Min();
    }
}

參考彥吉的練習C#新語法
> [name=Jim][time=Tue, Dec 13, 2022]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)