public class Solution {
    private int[][] grid;
    private int[][][] memo;
    public int cherryPickup(int[][] grid) {
        /**
         * 56/56 cases passed (23 ms)
         * Your runtime beats 54.69 % of java submissions
         * 这个算法是huahua https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-741-cherry-pickup/
         * 首先不能分开计算最优解，这样会变成贪婪算法，达不到最优解
         * 将一个来回的路程等效成2个人同时从右下角走到左上角
         * 获取状态转移公式将1人k=i+j跟另一个人k=p+q来实现
         * 时间复杂度 O(n^3)
         * 空间复杂度 O(n^3)
         */
        this.grid = grid;
        int m = grid.length;
        int n = grid[0].length;
        memo = new int[m][n][n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                Arrays.fill(memo[i][j], Integer.MIN_VALUE);
        return Math.max(0, dp(n - 1, m - 1, n - 1));
    }

    private int dp(int x1, int y1, int x2) {
        final int y2 = x1 + y1 - x2;
        // 边界控制
        if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0) return -1;
        // 遇到是-1，就跳过
        if (grid[y1][x1] < 0 || grid[y2][x2] < 0) return -1;
        // 同时达到终点
        if (x1 == 0 && y1 == 0) return grid[y1][x1];
        // 已经算过的值最优解，直接返回
        if (memo[y1][x1][x2] != Integer.MIN_VALUE) return memo[y1][x1][x2];
        memo[y1][x1][x2] = Math.max(
                // 由于限制了行动轨迹，去是往右跟往下，转换过来其实就是往左，往上
                // 回是往左，往上，这样同时从右下角出发，其实两个人都是只有两个方法，就有4种组合
                // 左，左 x1 - 1, y1, x2 - 1
                // 上, 上 x1, y1 - 1, x2 这里y2也是隐含在里面了,因为 x1 + y1 = x2 + y2
                // 上，左 x1, y1 - 1, x2 - 1
                // 左，上 x1 - 1, y1, x2
                Math.max(dp(x1 - 1, y1, x2 - 1), dp(x1, y1 - 1, x2)),
                Math.max(dp(x1, y1 - 1, x2 - 1), dp(x1 - 1, y1, x2)));

        if (memo[y1][x1][x2] >= 0) {
            // 同时达到一个点，让1用户拿到值，防止重复拿
            memo[y1][x1][x2] += grid[y1][x1];
            // 如果不是同一个点
            if (x1 != x2) memo[y1][x1][x2] += grid[y2][x2];
        }

        return memo[y1][x1][x2];
    }
}