Given a square grid of integers arr, a falling path with non-zero shifts is a choice of exactly one element from each row of arr, such that no two elements chosen in adjacent rows are in the same column.
Return the minimum sum of a falling path with non-zero shifts.
Example 1:
Input: arr = [[1,2,3],[4,5,6],[7,8,9]] Output: 13 Explanation: The possible falling paths are: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] The falling path with the smallest sum is [1,5,7], so the answer is 13.
Constraints:
1 <= arr.length == arr[i].length <= 200-99 <= arr[i][j] <= 99
Solution: DP
dp[i][j] = min(dp[i-1][k]), 1 <= k <= m, k != j
Time complexity: O(n^3)
Space complexity: O(n^2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int minFallingPathSum(vector<vector<int>>& arr) { constexpr int kInf = 1e6; for (int i = 1; i < arr.size(); ++i) for (int j = 0; j < arr[0].size(); ++j) { int m = kInf; for (int k = 0; k < arr[0].size(); ++k) { if (k == j) continue; m = min(m, arr[i - 1][k]); } arr[i][j] += m; } return *min_element(begin(arr.back()), end(arr.back())); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment