2022.7.10-----leetcode.741

    //题意可等价为两个人a,b同时走，到最后的最优解
    static int N = 51, INF = Integer.MIN_VALUE;
    static int[][][] f = new int[2 * N][N][N];//走了k步，a在i1行，b在i2行的解
    public int cherryPickup(int[][] g) {
        int n = g.length;
        //初始化矩阵为负无穷，如果某位置的上一步不可到达，那么该位置也不可到达，转移求最大时舍弃
        for (int k = 0; k <= 2 * n; k++) {
            for (int i1 = 0; i1 <= n; i1++) {
                for (int i2 = 0; i2 <= n; i2++) {
                    f[k][i1][i2] = INF;
                }
            }
        }
        //初始状态
        f[2][1][1] = g[0][0];
        //一共走2n-2步到终点
        for (int k = 3; k <= 2 * n; k++) {
            for (int i1 = 1; i1 <= n; i1++) {
                for (int i2 = 1; i2 <= n; i2++) {
                    int j1 = k - i1, j2 = k - i2;//对于第k步，已知所在行，可求出所在列
                    //对于第k步，i和j的范围会有限制，剔除不在正确范围的状态
                    if (j1 <= 0 || j1 > n || j2 <= 0 || j2 > n) continue;
                    //获取a,b当前位置得分
                    int A = g[i1 - 1][j1 - 1], B = g[i2 - 1][j2 - 1];
                    //当前位置不可到达
                    if (A == -1 || B == -1) continue;
                    //对于两个人，上一步所在位置有四种组合
                    int a = f[k - 1][i1 - 1][i2], b = f[k - 1][i1 - 1][i2 - 1], 
                    c = f[k - 1][i1][i2 - 1], d = f[k - 1][i1][i2];
                    //取上一步最大得分
                    int t = Math.max(Math.max(a, b), Math.max(c, d)) + A;
                    if (i1 != i2) t += B;//若当前两人在同一位置，不可重复计分
                    f[k][i1][i2] = t;
                }
            }
        }
        return f[2 * n][n][n] <= 0 ? 0 : f[2 * n][n][n];
    }