741. Cherry Pickup

T: O(n^3)
S: O(n^3)

class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        Integer[][][] memo = new Integer[n][n][n];
        return Math.max(0, dfs(grid, 0,0,0, memo)); // must use max(0, xxx), xxx maybe is Integer.MIN_VALUE
    }
    private int dfs(int[][] grid, int i, int j, int y, Integer[][][] memo) {
        int n = grid.length;
        int x = i + j - y;
        if (i >= n || j >= n || x >= n || y >= n || grid[i][j] == -1 || grid[x][y] == -1) {
            return Integer.MIN_VALUE;
        }
        if (i == n-1 && j == n-1) {
            return grid[i][j];
        }
        if (x == n-1 && y == n-1) {
            return grid[x][y];
        }
        if (memo[i][j][y] != null) {
            return memo[i][j][y];
        }

        int result = grid[i][j];
        if (i != x || j != y) { // not same position
            result += grid[x][y];
        }

        result += Math.max(
                        Math.max(
                            dfs(grid, i+1, j, y, memo), 
                            dfs(grid, i, j+1, y, memo)
                        ),
                        Math.max(
                            dfs(grid, i+1, j, y+1, memo), 
                            dfs(grid, i, j+1, y+1, memo)
                        ));
        
        memo[i][j][y] = result;
        return result;
    }
}

/**
question said: use 2 path from top left, and right bottom...to pickup the maximum number of cherry 
->  
actually it means find "2" path "from top left", and pickup the maximum number of cherry 

so we need memo[i][j][x][y]

but because x can calculate by x = i + j - y
-> so memo[i][j][y] -> O(n^3)
 */