Minimum-Falling-Path-Sum-II.java

class Solution {
    int N;
    public int minFallingPathSum(int[][] grid) {
        N = grid.length;
        int[][] dp = new int[N][N];

        for(int i = 0; i < N; i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        int minVal = Integer.MAX_VALUE;
        for(int col = 0; col < N; col++){
            minVal = Math.min(minVal, minSum(grid, 0, col, dp));
        }
        return minVal;
    }

    public int minSum(int[][] grid, int row, int col, int[][] dp){
        if(row == N - 1){
            return dp[row][col] = grid[row][col];
        }

        if(dp[row][col] != Integer.MAX_VALUE){
            return dp[row][col];
        }

        int minVal = Integer.MAX_VALUE;
        // Traverse all
        for(int j = 0; j < N; j++){
            if(j != col){
                minVal = Math.min(minVal, minSum(grid, row + 1, j, dp));
            }
        }
        return dp[row][col] = (grid[row][col] + minVal);
    }
}