Path and the largest

---

前言

链接：https://www.nowcoder.com/questionTerminal/8ecfe02124674e908b2aae65aad4efdf
来源：牛客网

给定一个矩阵matrix,先从左上角开始,每一步只能往右或者往下走,走到右下角.然后从右下角出发,每一步只能往上或者往左走,再回到左上角.任何一个位置的数字,只能获得一遍.返回最大路径和.

输入描述:
第一行输入两个整数M和N,M,N<=200
接下来M行,每行N个整数,represents the elements in the matrix

输出描述:
输出一个整数,表示最大路径和

解题思路

两个人A, B都从左下角走到右下角,都只能向下或者向右走,但是A跟B能做出不同的选择
如果,某一时刻,ABinto the same one 个格子,A和BOnly get one
Aafter walking,就认为BIt's the way back

A来到了a行b列, B来到了c行d列,If they jump into different grids.
In the case of only getting one,问你a跟bGet the overall maximum.

如果某一个位置A也来过,B也来过,AB-must come at the same time,而不会分先后
因为AB同步走

A variable can be omittedd,可以根据abc来推出d

代码

	public static void main(String[] args) {
    
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] matrix = new int[N][M];
		for (int i = 0; i < N; i++) {
    
			for (int j = 0; j < M; j++) {
    
				matrix[i][j] = sc.nextInt();
			}
		}
		int ans = cherryPickup(matrix);
		System.out.println(ans);
		sc.close();
	}
	
	public static int cherryPickup(int[][] grid) {
    
		int N = grid.length;
		int M = grid[0].length;
		int[][][] dp = new int[N][M][N];
		for (int i = 0; i < N; i++) {
    
			for (int j = 0; j < M; j++) {
    
				for (int k = 0; k < N; k++) {
    
					dp[i][j][k] = Integer.MIN_VALUE;
				}
			}
		}
		int ans = process(grid, 0, 0, 0, dp);
		return ans < 0 ? 0 : ans;
	}

	public static int process(int[][] grid, int x1, int y1, int x2, int[][][] dp) {
    
		if (x1 == grid.length || y1 == grid[0].length || x2 == grid.length || x1 + y1 - x2 == grid[0].length) {
    
			return Integer.MIN_VALUE;
		}
		if (dp[x1][y1][x2] != Integer.MIN_VALUE) {
    
			return dp[x1][y1][x2];
		}
		if (x1 == grid.length - 1 && y1 == grid[0].length - 1) {
    
			dp[x1][y1][x2] = grid[x1][y1];
			return dp[x1][y1][x2];
		}
		int next = Integer.MIN_VALUE;
		next = Math.max(next, process(grid, x1 + 1, y1, x2 + 1, dp));
		next = Math.max(next, process(grid, x1 + 1, y1, x2, dp));
		next = Math.max(next, process(grid, x1, y1 + 1, x2, dp));
		next = Math.max(next, process(grid, x1, y1 + 1, x2 + 1, dp));
		if (grid[x1][y1] == -1 || grid[x2][x1 + y1 - x2] == -1 || next == -1) {
    
			dp[x1][y1][x2] = -1;
			return dp[x1][y1][x2];
		}
		if (x1 == x2) {
    
			dp[x1][y1][x2] = grid[x1][y1] + next;
			return dp[x1][y1][x2];
		}
		dp[x1][y1][x2] = grid[x1][y1] + grid[x2][x1 + y1 - x2] + next;
		return dp[x1][y1][x2];
	}