931. Minimum Falling Path Sum

Medium (Trung bình) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

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

🧠 Thuật Toán & Kỹ Thuật

Bit Manipulation (Thao tác bit)Matrix (Ma trận)

⏱️ Thời gian O(n²)

💾 Không gian O(n)

💻 Lời Giải

C++ 0931-minimum-falling-path-sum.cpp

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] += min({
                    matrix[i - 1][j], 
                    matrix[i - 1][max(0, j - 1)], 
                    matrix[i - 1][min(n - 1, j + 1)]
                });
            }
        }
        
        return *min_element(matrix[n - 1].begin(), matrix[n - 1].end());
    }
};

Python 0931-minimum-falling-path-sum.py

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