最大路径和

[编程题]最大路径和

热度指数：853 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行输入两个整数M和N，M,N<=200
接下来M行，每行N个整数，表示矩阵中元素

输出描述:

输出一个整数，表示最大路径和

示例1

输入

5 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1

输出

示例2

输入

5 10
1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1
1 0 0 0 1 0 0 0 1 0
0 0 0 0 1 1 1 1 0 1

输出

算法知识视频讲解

逆臣可以改

发表于 2022-02-07 23:43:08

有点抽象... 把问题转化为左上走到右下，走两次，所能获得的共同最大值。统计的是两条路，每一步的点(x1,y1) 和 (x2,y2) 时的路径和，由于是同步移动的，满足x1+y1 = x2+y2，故可以省略y2. 每个路径都可以选择向右或者向下，那么每一步会衍生出4中情况，都要进递归。如果边展开全文