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

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

本文概述

``````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``