原题链接在这里：https://leetcode.com/problems/minimum-falling-path-sum/
题目：
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题解：
For each cell A[i][j], the minimum falling path sum ending at this cell = A[i][j]+ Min(minimum sum ending on its upper left, minimum sum ending on its upper, minimum sum ending on it upper right).
Could use dp to cash previous value.
Time Complexity: O(m*n). m = A.length. n = A[0].length.
Space: O(m*n).
AC Java:
1 class Solution { 2 public int minFallingPathSum(int[][] A) { 3 if(A == null || A.length == 0 || A[0].length == 0){ 4 return 0; 5 } 6 7 int res = Integer.MAX_VALUE; 8 int m = A.length; 9 int n = A[0].length; 10 int [][] dp = new int[m+1][n]; 11 12 for(int i = 1; i<=m; i++){ 13 for(int j = 0; j<n; j++){ 14 int leftUp = j==0 ? dp[i-1][j] : dp[i-1][j-1]; 15 int rightUp = j == n-1 ? dp[i-1][j] : dp[i-1][j+1]; 16 dp[i][j] = A[i-1][j] + Math.min(leftUp, Math.min(dp[i-1][j], rightUp)); 17 if(i == m){ 18 res = Math.min(res, dp[i][j]); 19 } 20 } 21 } 22 23 return res; 24 } 25 }
Could operate on original A.
Time Complexity: O(m*n).
Space: O(1).
AC Java:
1 class Solution { 2 public int minFallingPathSum(int[][] A) { 3 if(A == null || A.length == 0 || A[0].length == 0){ 4 return 0; 5 } 6 7 int res = Integer.MAX_VALUE; 8 int m = A.length; 9 int n = A[0].length; 10 11 if(m == 1){ 12 for(int j = 0; j<n; j++){ 13 res = Math.min(res, A[0][j]); 14 } 15 16 return res; 17 } 18 19 for(int i = 1; i<m; i++){ 20 for(int j = 0; j<n; j++){ 21 int leftUp = j==0 ? A[i-1][j] : A[i-1][j-1]; 22 int rightUp = j == n-1 ? A[i-1][j] : A[i-1][j+1]; 23 A[i][j] += Math.min(leftUp, Math.min(A[i-1][j], rightUp)); 24 if(i == m-1){ 25 res = Math.min(res, A[i][j]); 26 } 27 } 28 } 29 30 return res; 31 } 32 }
LeetCode 931. Minimum Falling Path Sum
原文：https://www.cnblogs.com/Dylan-Java-NYC/p/11437777.html