本文概述

• 建议：在继续解决方案之前, 请先在{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)

推荐阅读

• 

  学生成绩查询分析系统,南昊学生成绩查询系统
• 

  你永远也叫不醒一个在装睡的人
• 

  定量分析产品质量
• 

  冬天下雪打雷的迷信说法有什么预兆？
• 

  男人用这种方式对你 男人想让女人主动分手的表现
• 

  eyefunny是什么牌子
• 

  单因素方差分析f是什么,双因素方差分析是什么
• 

  南京鼓楼医院门诊预约挂号方式有哪些
• 

  萌新阴阳师求式神培养方案？
• 

  无法抵达的MU5735，人在哪？
• 

  分享是最好的成长方式
• 

  部落冲突的十本一般怎么配兵胜率比较高？
• 

  中国最好的mpv汽车 中国品牌能造出好的mpv吗
• 

  奶香型婴儿沐浴露哪家好？推荐奶香型婴儿沐浴露品牌
• 

  夏天荷花盛开,而描写荷花诗词非常多,你最喜欢哪一首？
• 

  谈谈为什么选择护理专业 为什么选择当护士
• 

  没卸防晒睡觉会怎样
• 

  森雅r7发电机皮带绕法 森雅r7发动机皮带图解
• 

  小米手机移动网络不可用怎么办
• 

  台达触摸屏

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