本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Java
• Python3
• C#

给定维度矩阵N * M。任务是找到以下路径的最大和arr [0] [0]toarr [N – 1] [M – 1]然后从arr [N – 1] [M – 1]toarr [0] [0].
在从arr [0] [0]toarr [N – 1] [M – 1], 你可以在上下方向以及从arr [N – 1] [M – 1]toarr [0] [0], 你可以上下移动。
注意：两条路径都不能相等, 即必须至少有一个像元arr [i] [j]这在两条路径中都不常见。
例子：

Input: mat[][]= {{1, 0, 3, -1}, {3, 5, 1, -2}, {-2, 0, 1, 1}, {2, 1, -1, 1}}Output: 16Maximum sum on path from arr[0][0] to arr[3][3] = 1 + 3 + 5 + 1 + 1 + 1 + 1 = 13Maximum sum on path from arr[3][3] to arr[0][0] = 3Total path sum = 13 + 3 = 16Input: mat[][]= {{1, 0}, {1, 1}}Output: 3

推荐：请尝试使用{IDE}首先, 在继续解决方案之前。方法：
这个问题有点类似于
最低成本路径
问题是, 除了在本问题中, 将找到两个具有最大和的路径。另外, 我们需要注意两条路径上的单元仅对总和贡献一次。
首先要注意的是
arr [N – 1] [M – 1]
to
arr [0] [0]
只是别的途径而已
arr [0] [0]
to
arr [N – 1] [M – 1]
。因此, 我们必须找到两条路径
arr [0] [0]
to
arr [N – 1] [M – 1]
最大金额。
与最小成本路径问题类似, 我们从
arr [0] [0]
【矩阵从上到下以及到后的最大求和路径】在一起并递归到矩阵的相邻单元, 直到我们到达
arr [N – 1] [M – 1]
。为了确保一个单元格的贡献不止一次, 我们检查两条路径上的当前单元格是否相同。如果它们相同, 则仅将其添加到答案一次。
下面是上述方法的实现：
C ++

// C++ implementation of the approach #include < bits/stdc++.h> using namespace std; // Input matrix int n = 4, m = 4; int arr[4][4] = { { 1, 0, 3, -1 }, { 3, 5, 1, -2 }, { -2, 0, 1, 1 }, { 2, 1, -1, 1 } }; // DP matrix int cache[5][5][5]; // Function to return the sum of the cells // arr[i1][j1] and arr[i2][j2] int sum( int i1, int j1, int i2, int j2) { if (i1 == i2 & & j1 == j2) { return arr[i1][j1]; } return arr[i1][j1] + arr[i2][j2]; }// Recursive function to return the // required maximum cost path int maxSumPath( int i1, int j1, int i2) {// Column number of second path int j2 = i1 + j1 - i2; // Base Case if (i1 > = n || i2 > = n || j1 > = m || j2 > = m) { return 0; }// If already calculated, return from DP matrix if (cache[i1][j1][i2] != -1) { return cache[i1][j1][i2]; } int ans = INT_MIN; // Recurring for neighbouring cells of both paths together ans = max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2)); ans = max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2)); ans = max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2)); ans = max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2)); // Saving result to the DP matrix for current state cache[i1][j1][i2] = ans; return ans; }// Driver code int main() { memset (cache, -1, sizeof (cache)); cout < < maxSumPath(0, 0, 0); return 0; }

Java

// Java implementation of the approach import java.util.*; class GFG { // Input matrix static int n = 4 , m = 4 ; static int arr[][] = { { 1 , 0 , 3 , - 1 }, { 3 , 5 , 1 , - 2 }, { - 2 , 0 , 1 , 1 }, { 2 , 1 , - 1 , 1 } }; // DP matrix static int cache[][][] = new int [ 5 ][ 5 ][ 5 ]; // Function to return the sum of the cells // arr[i1][j1] and arr[i2][j2] static int sum( int i1, int j1, int i2, int j2) { if (i1 == i2 & & j1 == j2) { return arr[i1][j1]; } return arr[i1][j1] + arr[i2][j2]; }// Recursive function to return the // required maximum cost path static int maxSumPath( int i1, int j1, int i2) {// Column number of second path int j2 = i1 + j1 - i2; // Base Case if (i1 > = n || i2 > = n || j1 > = m || j2 > = m) { return 0 ; }// If already calculated, return from DP matrix if (cache[i1][j1][i2] != - 1 ) { return cache[i1][j1][i2]; } int ans = Integer.MIN_VALUE; // Recurring for neighbouring cells of both paths together ans = Math.max(ans, maxSumPath(i1 + 1 , j1, i2 + 1 ) + sum(i1, j1, i2, j2)); ans = Math.max(ans, maxSumPath(i1, j1 + 1 , i2) + sum(i1, j1, i2, j2)); ans = Math.max(ans, maxSumPath(i1, j1 + 1 , i2 + 1 ) + sum(i1, j1, i2, j2)); ans = Math.max(ans, maxSumPath(i1 + 1 , j1, i2) + sum(i1, j1, i2, j2)); // Saving result to the DP matrix for current state cache[i1][j1][i2] = ans; return ans; }// Driver code public static void main(String args[]) { //set initial value for ( int i= 0 ; i< 5 ; i++) for ( int i1= 0 ; i1< 5 ; i1++) for ( int i2= 0 ; i2< 5 ; i2++) cache[i][i1][i2]=- 1 ; System.out.println( maxSumPath( 0 , 0 , 0 )); } }// This code is contributed by Arnab Kundu

Python3

# Python 3 implementation of the approach import sys# Input matrix n = 4 m = 4 arr = [[ 1 , 0 , 3 , - 1 ], [ 3 , 5 , 1 , - 2 ], [ - 2 , 0 , 1 , 1 ], [ 2 , 1 , - 1 , 1 ]]# DP matrix cache = [[[ - 1 for i in range ( 5 )] for j in range ( 5 )] for k in range ( 5 )]# Function to return the sum of the cells # arr[i1][j1] and arr[i2][j2] def sum (i1, j1, i2, j2): if (i1 = = i2 and j1 = = j2): return arr[i1][j1] return arr[i1][j1] + arr[i2][j2]# Recursive function to return the # required maximum cost path def maxSumPath(i1, j1, i2):# Column number of second path j2 = i1 + j1 - i2# Base Case if (i1 > = n or i2 > = n or j1 > = m or j2 > = m): return 0# If already calculated, return from DP matrix if (cache[i1][j1][i2] ! = - 1 ): return cache[i1][j1][i2] ans = - sys.maxsize - 1# Recurring for neighbouring cells of both paths together ans = max (ans, maxSumPath(i1 + 1 , j1, i2 + 1 ) + sum (i1, j1, i2, j2)) ans = max (ans, maxSumPath(i1, j1 + 1 , i2) + sum (i1, j1, i2, j2)) ans = max (ans, maxSumPath(i1, j1 + 1 , i2 + 1 ) + sum (i1, j1, i2, j2)) ans = max (ans, maxSumPath(i1 + 1 , j1, i2) + sum (i1, j1, i2, j2))# Saving result to the DP matrix for current state cache[i1][j1][i2] = ansreturn ans# Driver code if __name__ = = '__main__' : print (maxSumPath( 0 , 0 , 0 ))# This code is contributed by # Surendra_Gangwar

C#

// C# implementation of the approach using System; class GFG { // Input matrix static int n = 4, m = 4; static int [, ]arr = { { 1, 0, 3, -1 }, { 3, 5, 1, -2 }, { -2, 0, 1, 1 }, { 2, 1, -1, 1 } }; // DP matrix static int [, , ]cache = new int [5, 5, 5]; // Function to return the sum of the cells // arr[i1][j1] and arr[i2][j2] static int sum( int i1, int j1, int i2, int j2) { if (i1 == i2 & & j1 == j2) { return arr[i1, j1]; } return arr[i1, j1] + arr[i2, j2]; }// Recursive function to return the // required maximum cost path static int maxSumPath( int i1, int j1, int i2) {// Column number of second path int j2 = i1 + j1 - i2; // Base Case if (i1 > = n || i2 > = n || j1 > = m || j2 > = m) { return 0; }// If already calculated, return from DP matrix if (cache[i1, j1, i2] != -1) { return cache[i1, j1, i2]; } int ans = int .MinValue; // Recurring for neighbouring cells of both paths together ans = Math.Max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2)); ans = Math.Max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2)); ans = Math.Max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2)); ans = Math.Max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2)); // Saving result to the DP matrix for current state cache[i1, j1, i2] = ans; return ans; }// Driver code public static void Main(String []args) { //set initial value for ( int i = 0; i < 5; i++) for ( int i1 = 0; i1 < 5; i1++) for ( int i2 = 0; i2 < 5; i2++) cache[i, i1, i2]=-1; Console.WriteLine( maxSumPath(0, 0, 0)); } }// This code contributed by Rajput-Ji

输出如下：

16

时间复杂度：上2)* M)

推荐阅读

• 

  你们认为诗仙李白最好的一首诗是哪一首？
• 

  一天喝多少牛奶合适？
• 

  青芒的热量高吗
• 

  花胶有什么营养价值
• 

  土大黄的功效与作用 土大黄的副作用
• 

  美国冲突升级!武装民兵冲进议会大厦,议员吓的穿防弹衣上班,州长命令被废,大乱了吗？
• 

  最新热门的12个最佳博客平台合集（以及如何选择一个）
• 

  买笔记本电脑,处理器是选择i5还是i7？
• 

  妒组词语 妒有哪些组词呢
• 

  熊童子简笔画
• 

  Photoshop制作沧桑颓废的城市海报
• 

  手机停机怎么连接网络，手机停机怎么连接网络电视
• 

  176升冰箱购买指南及故障维修解决方案
• 

  早晨八点半
• 

  升级换代，让您的打印更高效 epsonL3153变成2710
• 

  海带有味道了还能吃吗
• 

  照门是什么意思 照门的含义
• 

  获嘉天气30天 获嘉天气预报
• 

  核酸检测假阳性怎么处理
• 

  分享一首小诗（相信）

• PHP rewinddir()函数用法介绍
• jQuery #id选择器用法指南
• 如何在JavaScript中存储key value数组（（键值对））
• vue.js框架快速入门简明教程(七)（自定义指令）
• JavaScript的函数参数和arguments是什么（）
• 详解JavaScript基本数据类型和引用类型的区别、值传递和引用传递
• vue.js框架快速入门简明教程(六)（组件）
• JavaScript基础快速入门教程（八）（包装数据类型、日期对象、Math对象和全局对象）
• JavaScript基础快速入门教程（七）（数组创建、遍历数组、数据结构和算法和实例）