Minimum Falling Path Sum II LeetCode solution in Java

1
class Solution {
2
  // Recursion
3
  /* public int minFallingPathSum(int[][] grid) {
4
      int n=grid.length;
5
      if(n==1) return grid[0][0];
6
      int ans = 10000000;
7
      for(int i=0 ; i<n ; i++){
8
          ans = Math.min(ans , grid[0][i] + helper(grid , n , 1 , i));
9
      }
10
      return ans;
11
  }
12

13
  private int helper(int[][] grid , int n , int i , int last){
14
      if( i == n-1 ){
15
          int min = 100;
16
          for(int k=0 ; k<n ; k++){
17
              if(k!=last){
18
                  min = Math.min( grid[n-1][k] , min);
19
              }
20
          }
21
          return min;
22
      }
23

24
      int min = 100000000;
25
      for(int k=0 ; k<n ; k++){
26
          if(k != last){
27
              min = Math.min( min ,grid[i][k] +  helper(grid , n , i+1 , k) );
28
          }
29
      }
30

31
      return min;
32
  }
33
  */
34

35
  // DP MEMOIZATION
36
  public int minFallingPathSum(int[][] grid) {
37
    int n = grid.length;
38
    if (n == 1) return grid[0][0];
39
    int[][] dp = new int[n][n];
40
    for (int i = 0; i < n; i++) {
41
      for (int j = 0; j < n; j++) {
42
        dp[i][j] = -1;
43
      }
44
    }
45

46
    int ans = 10000000;
47
    for (int i = 0; i < n; i++) {
48
      ans = Math.min(ans, grid[0][i] + helper(grid, n, 1, i, dp));
49
    }
50
    return ans;
51
  }
52

53
  private int helper(int[][] grid, int n, int i, int last, int[][] dp) {
54
    if (i == n - 1) {
55
      int min = 100;
56
      for (int k = 0; k < n; k++) {
57
        if (k != last) {
58
          min = Math.min(grid[n - 1][k], min);
59
        }
60
      }
61
      return min;
62
    }
63
    if (dp[i][last] != -1) return dp[i][last];
64
    int min = 100000000;
65
    for (int k = 0; k < n; k++) {
66
      if (k != last) {
67
        min = Math.min(min, grid[i][k] + helper(grid, n, i + 1, k, dp));
68
      }
69
    }
70

71
    dp[i][last] = min;
72
    return dp[i][last];
73
  }
74
}