Problem
Given aĀ squareĀ array of integersĀ A
, we want theĀ minimumĀ sum of aĀ falling pathĀ throughĀ A
.
A falling path starts at any element in the first row, and chooses one element from each row.Ā The next row’s choice must be in a column that is different from the previous row’s column by at most one.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]] Output: 12 Explanation: The possible falling paths are:
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum isĀ [1,4,7]
, so the answer isĀ 12
.
Note:
1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100
Solution: DP
Time complexity: O(mn)
Space complexity: O(mn)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 12 ms class Solution { public: int minFallingPathSum(vector<vector<int>>& A) { int n = A.size(); int m = A[0].size(); vector<vector<int>> dp(n + 2, vector<int>(m + 2)); for (int i = 1; i <= n; ++i) { dp[i][0] = dp[i][m + 1] = INT_MAX; for (int j = 1; j <= m; ++j) dp[i][j] = *min_element(dp[i - 1].begin() + j - 1, dp[i - 1].begin() + j + 2) + A[i - 1][j - 1]; } return *min_element(dp[n].begin() + 1, dp[n].end() - 1); } }; |
C++/in place
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 12 ms class Solution { public: int minFallingPathSum(vector<vector<int>>& A) { int n = A.size(); int m = A[0].size(); for (int i = 1; i < n; ++i) for (int j = 0; j < m; ++j) { int sum = A[i - 1][j]; if (j > 0) sum = min(sum, A[i - 1][j - 1]); if (j < m - 1) sum = min(sum, A[i - 1][j + 1]); A[i][j] += sum; } return *min_element(begin(A.back()), end(A.back())); } }; |