原题链接在这里：
题目：
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: 12Explanation: 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 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