文章目录
前言
解题思路
代码
前言
链接:https://www.nowcoder.com/questionTerminal/8ecfe02124674e908b2aae65aad4efdf
来源:牛客网
给定一个矩阵matrix,先从左上角开始,每一步只能往右或者往下走,走到右下角。然后从右下角出发,每一步只能往上或者往左走,再回到左上角。任何一个位置的数字,只能获得一遍。返回最大路径和。
输入描述:
第一行输入两个整数M和N,M,N<=200
接下来M行,每行N个整数,表示矩阵中元素
输出描述:
输出一个整数,表示最大路径和
解题思路
两个人A, B都从左下角走到右下角,都只能向下或者向右走,但是A跟B能做出不同的选择
如果,某一时刻,AB进入相同的一 个格子,A和B只获得一份
A走到之后,就认为B就是回来的路径
A来到了a行b列, B来到了c行d列,如果它们跳进不同的格子里。
只获得一个的情况下,问你a跟b获得整体的最大。
如果某一个位置A也来过,B也来过,AB-定是同时来的,而不会分先后
因为AB同步走
可以省掉一个变量d,可以根据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) {