min path sum hard

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

        // Initialize dp with -1
        for (int[] row : dp)
            Arrays.fill(row, -1);

        int minSum = Integer.MAX_VALUE;

        // Try all columns in the first row
        for (int col = 0; col < n; col++) {
            minSum = Math.min(minSum, helper(grid, 0, col, dp));
        }

        return minSum;
    }

    // Recursive helper with memoization
    private int helper(int[][] grid, int row, int col, int[][] dp) {
        int n = grid.length;

        // Base case: last row
        if (row == n - 1) return grid[row][col];

        // If already computed
        if (dp[row][col] != -1) return dp[row][col];

        int min = Integer.MAX_VALUE;

        // Try all columns in next row except the current column
        for (int nextCol = 0; nextCol < n; nextCol++) {
            if (nextCol != col) {
                min = Math.min(min, helper(grid, row + 1, nextCol, dp));
            }
        }



        return dp[row][col] = grid[row][col] + min;
    }
}