当前位置:网站首页>最大路径和
最大路径和
2022-07-31 01:38:00 【小卢要刷力扣题】
前言
链接: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) {
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];
}
边栏推荐
猜你喜欢
Centos 7.9 install PostgreSQL14.4 steps
九州云入选“可信云最新评估体系及2022年通过评估企业名单”
最高月薪20K?平均薪资近万...在华为子公司工作是什么体验?
Centos 7.9安装PostgreSQL14.4步骤
VSCode插件:嵌套注释
数字图像隐写术之卡方分布
tensorflow与GPU版本对应安装问题
GCC Rust获批将被纳入主线代码库,或将于GCC 13中与大家见面
【Map与Set】之LeetCode&牛客练习
pycharm重命名后无法运行(报错: can‘t open file......No such file or directory)
随机推荐
MySQL stored procedure
TiDB之rawkv升级之路v5.0.4--&gt;v6.1.0
What have I experienced when I won the offer of BAT and TMD technical experts?
GCC Rust获批将被纳入主线代码库,或将于GCC 13中与大家见面
Bert usage and word prediction based on Keras_bert model
Distributed. Idempotency
ROS Action communication
Google官方控件ShapeableImageView使用
Mysql: Invalid default value for TIMESTAMP
Jiuzhou Cloud was selected into the "Trusted Cloud's Latest Evaluation System and the List of Enterprises Passing the Evaluation in 2022"
射频器件的基本参数2
《实战》基于电商领域的词性提取及其决策树模型建模
rpm install postgresql12
软件测试工作3年了,谈谈我是如何从刚入门进阶到自动化测试的?
进程间通信学习笔记
孩子的编程启蒙好伙伴,自己动手打造小世界,长毛象教育AI百变编程积木套件上手
有没有可以做副业可以日入300元方法?
Gateway路由的配置方式
Fiddler抓包模拟弱网络环境测试
软件测试要达到一个什么水平才能找到一份9K的工作?