package leetcode;

/**
 * https://leetcode.com/problems/minimum-falling-path-sum/
 */
public class Problem931 {
    public int minFallingPathSum(int[][] A) {
        int maxRow = A.length;
        int maxCol = A.length > 0 ? A[0].length : 0;
        int min = Integer.MAX_VALUE;
//        for (int col = 0; col < maxCol; col++) {
//            min = Math.min(min, minFaillingPathSum(A, maxRow, maxCol, 0, col));
//        }
        min = Math.min(min, minFaillingPathSum(A, maxRow, maxCol, 0, 0));
        return min;
    }

    private static int minFaillingPathSum(int[][] a, int maxRow, int maxCol, int row, int col) {
        if (row < 0 || col < 0 || row >= maxRow || col >= maxCol) {
            return 0;
        }
        int value = a[row][col];
        int min = Integer.MAX_VALUE;
        min = Math.min(min, minFaillingPathSum(a, maxRow, maxCol, row + 1, col - 1) + value);
        min = Math.min(min, minFaillingPathSum(a, maxRow, maxCol, row + 1, col) + value);
        min = Math.min(min, minFaillingPathSum(a, maxRow, maxCol, row + 1, col + 1) + value);
        return min;
    }

    public static void main(String[] args) {
        Problem931 prob = new Problem931();
        System.out.println(prob.minFallingPathSum(new int[][]{
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        })); // 12
    }
}

@@ -272,18 +272,80 @@
 _VALUE;%0A
-//
+        Integer%5B%5D%5B%5D memo = new Integer%5BmaxRow + 1%5D%5BmaxCol + 1%5D;%0A
         
@@ -385,18 +385,16 @@
 ol++) %7B%0A
-//
         
@@ -465,14 +465,18 @@
  col
+, memo
 ));%0A
-//
     
@@ -485,82 +485,8 @@
   %7D%0A
-        min = Math.min(min, minFaillingPathSum(A, maxRow, maxCol, 0, 0));%0A
     
@@ -601,16 +601,76 @@
  int col
+,%0A                                          Integer%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -749,16 +749,187 @@
     
-return 0
+if (row %3C maxRow) %7B%0A                return Integer.MAX_VALUE;%0A            %7D%0A            return 0;%0A        %7D%0A        if (memo%5Brow%5D%5Bcol%5D != null) %7B%0A            return memo%5Brow%5D%5Bcol%5D
 ;%0A  
@@ -1088,25 +1088,23 @@
  col - 1
-) + value
+, memo)
 );%0A     
@@ -1176,25 +1176,23 @@
 + 1, col
-) + value
+, memo)
 );%0A     
@@ -1272,17 +1272,15 @@
  + 1
-) + value
+, memo)
 );%0A 
@@ -1290,265 +1290,71 @@
     
-return min;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem931 prob = new Problem931();%0A        System.out.println(prob.minFallingPathSum(new int%5B%5D%5B%5D%7B%0A            %7B1, 2, 3%7D,%0A            %7B4, 5, 6%7D,%0A            %7B7, 8, 9%7D%0A        %7D)); // 12
+min += value;%0A        memo%5Brow%5D%5Bcol%5D = min;%0A        return min;
 %0A   

Solve problem 931