Skip to content

LeetCode: 931-Minimum Falling Path Sum 解題紀錄

Last Updated on 2022-12-13 by Clay

題目

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

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

題目給定一個正方形尺寸為 n 的陣列,我們要找出一條路徑,該路徑上的值加總必須為陣列中可能路徑的最小值。

路徑的定義則是,假設我們現在位於第 i 個位置,我們往下走,只能從下一層的 i-1 和 i+1 的範圍內選一個點。通俗來講,就是能斜一格來走。


解題思路

累積前一層的最小值

我知道這題應該存在 DP 解,但我還是採用了直接從前一層選擇最小值選點的方式,直接加在當前值的方法。

這樣一來,我們一層層地累積最小值,在最後一層選擇最小的選點,即是我們要的答案。


累積前一層的最小值 複雜度

Time ComplexityO(n^2)
Space ComplexityO(1)


C++ 範例程式碼

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        // Init
        int dx[3] = {-1, 0, 1};
        int n = matrix.size();

        // Accumulate the minimum value of last row
        for (int i=1; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                int temp = INT_MAX;
                for (int& x: dx) {
                    if (j+x < 0 || j+x >= n) {
                        continue;
                    }
                    temp = min(temp, matrix[i-1][j+x]);
                }
                matrix[i][j] += temp;
            }
        }

        return *min_element(matrix.back().begin(), matrix.back().end());
    }
};



Python 範例程式碼

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        # Init
        N = len(matrix)

        # Accumulate the minimum value of previous row
        for i in range(1, N):
            for j in range(N):
                left = max(0, j-1)
                right = min(N-1, j+1)
                matrix[i][j] += min(matrix[i-1][left:right+1])

        return min(matrix[-1])

References


Read More

Leave a Reply