矩阵从上到下以及到后的最大求和路径

2021年3月9日16:23:38 发表评论 781 次浏览

本文概述

给定维度矩阵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: 16

Maximum sum on path from arr[0][0] to arr[3][3] 
= 1 + 3 + 5 + 1 + 1 + 1 + 1 = 13
Maximum sum on path from arr[3][3] to arr[0][0] = 3
Total path sum = 13 + 3 = 16

Input: 
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] = ans
  
     return 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)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: