931.Minimum Falling Path Sum

tags: Medium,Array,DP,Matrix

931. 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]);
}

Marsgoat 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;
    }
};

Yen-Chi ChenTue, 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])

Yen-Chi ChenTue, 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
KobeTue, 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#新語法

JimTue, Dec 13, 2022

Reference

回到題目列表