2022.7.10-----leetcode. seven hundred and forty-one

    // The meaning of the question can be equivalent to two people a,b Go at the same time , To the final optimal solution 
    static int N = 51, INF = Integer.MIN_VALUE;
    static int[][][] f = new int[2 * N][N][N];// go k Step ,a stay i1 That's ok ,b stay i2 Solution of row 
    public int cherryPickup(int[][] g) {
        int n = g.length;
        // The initialization matrix is negative infinite , If the last step of a certain position cannot be reached , Then the location cannot be reached , Discard when transferring to maximize 
        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;
                }
            }
        }
        // The initial state 
        f[2][1][1] = g[0][0];
        // Let's go 2n-2 Step to the end 
        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;// For the first k Step , Known line , Can find the column 
                    // For the first k Step ,i and j There will be limits to the scope of , Eliminate the state that is not in the correct range 
                    if (j1 <= 0 || j1 > n || j2 <= 0 || j2 > n) continue;
                    // obtain a,b Current position score 
                    int A = g[i1 - 1][j1 - 1], B = g[i2 - 1][j2 - 1];
                    // The current location is unreachable 
                    if (A == -1 || B == -1) continue;
                    // For two people , There are four combinations where the previous step is located 
                    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];
                    // Take the maximum score of the previous step 
                    int t = Math.max(Math.max(a, b), Math.max(c, d)) + A;
                    if (i1 != i2) t += B;// If two people are currently in the same position , No repeated scoring 
                    f[k][i1][i2] = t;
                }
            }
        }
        return f[2 * n][n][n] <= 0 ? 0 : f[2 * n][n][n];
    }