[LeetCode] 1463. Cherry Pickup II

 Problem : https://leetcode.com/problems/cherry-pickup-ii/

The final result only depends on the track of robot 1 and robot 2. The order of robot movement won't affect the final result. But if we move the 2 robots separately, the optimal track of one robot depends on the other robot's track. We will need to record the whole track of one robot to get the optimal track of another robot.

If we move the 2 robots synchronously, the optimal result only depends on the new position of the 2 robots on the next row.

class Solution {
    int ROW;
    int COLUMN;
    
    int[][] grid;
    int[][][] memo;
    
    int[] diff = new int[] {-1, 0, 1};
    
    public int cherryPickup(int[][] grid) {
        this.ROW = grid.length;
        this.COLUMN = grid[0].length;
        this.grid = grid;
        this.memo = new int[ROW][COLUMN][COLUMN];
        
        return helper(0, 0, COLUMN-1);
    }
    
    int helper(int y, int x1, int x2) {
        if (y >= ROW || x1 < 0 || x1 >= COLUMN || x2 < 0 || x2 >= COLUMN) {
            return 0;
        }
        
        if (memo[y][x1][x2] != 0) {
            return memo[y][x1][x2];
        }
        
        int result = x1 != x2 ? grid[y][x1] + grid[y][x2] : grid[y][x1];
        
        int tmp = 0;
        
        for (int dx1 : diff) {
            for (int dx2: diff) {
                tmp = Math.max(tmp, helper(y+1, x1 + dx1, x2 + dx2));
            } 
        }
        
        memo[y][x1][x2] = result + tmp;
        return memo[y][x1][x2];
    }
}