LeetCode-1289. Minimum Falling Path Sum II

LeetCode-1289. Minimum Falling Path Sum II

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: 13Explanation: 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​​

​​题解：​​

​​dag模型​​

class Solution {public: int minFallingPathSum(vector>& arr) { if (arr.empty() == true) { return 0; } int n = arr.size(); int res = INT_MAX; vector> dp(n, vector(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == 0) { dp[i][j] = arr[i][j]; } else { int prev = INT_MAX; for (int k = 0; k < n; k++) { if (k != j) { prev = min(prev, dp[i - 1][k]); } } dp[i][j] = arr[i][j] + prev; } } } for (int i = 0; i < n; i++) { res = min(res, dp[n - 1][i]); } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。