C ++程序中矩阵从上到下再返回的最大求和路径
在这个问题中，我们得到了大小为nXm的矩阵mat[][]。我们的任务是创建一个程序，以从上到下以及从后到后的矩阵中查找最大求和路径。
问题描述-我们需要找到从左上到右下再返回的最大路径总和。
有效的移动
From mat[0][0] to mat[n−1][m−1]: Right (mat[i][j] to mat[i][j+1]) and Down (mat[i][j] to mat[i+1][j]). From mat[n−1][m−1] to mat[0][0]: left (mat[i][j] to mat[i][j−1]) and up (mat[i][j] to mat[i−1][j]).
重要的一点是，两条路径不能相同。两条路径中应该有一个或多个不同的元素。
让我们举个例子来了解这个问题，
输入项
mat[][] = {
{1, 2, 4},
{3, 0, 1},
{5, −1, −1}
}输出结果
15
说明
Path from mat[0][0] to mat[n−1][m−1]: 1 + 3 + 5 − 1 − 1 = 7 Path from mat[n−1][m−1] to mat[0][0]: + 1 + 4 + 2 + 1 = 8 Sum = 7 + 8 = 15
解决方法
为了解决该问题，我们需要找到两条路径（一条从mat[0][0]到mat[n-1][m-1]，另一条从mat[n-1][m-1]到mat[0][0]）。但是更好的事情是找到从mat[0][0]到mat[n-1][m-1]的两条不同路径的和。为此，我们将从mat[0][0]开始，通过找到下一个最有希望的元素，直到它们到达路径的末端，来找到两条路径。然后返回两者的总和。我们需要检查的一件事是找到一个单元格是否不在两条路径上，因为需要两条不同的路径。
示例
该程序说明了我们解决方案的工作原理，
#include <bits/stdc++.h>
using namespace std;
#define row 3
int CalcNodeDiff(int mat[][row], int path1x, int path1y, int path2x, int
path2y) {
if (path1x == path2x && path1y == path2y) {
return mat[path1x][path1y];
}
return mat[path1x][path1y] + mat[path2x][path2y];
}
int calcMaxPathSumOfMat(int mat[][row], int path1x, int path1y, int
path2x, int n) {
int pathSumDP[5][5][5];
memset(pathSumDP, −1, sizeof(pathSumDP));
int path2y = path1x + path1y − path2x;
int maxPathSum = −10000;
if (path1x >= n || path2x >= n || path1y >= row || path2y >= row)
return 0;
if (pathSumDP[path1x][path1y][path2x] != −1)
return pathSumDP[path1x][path1y][path2x];
maxPathSum = max(maxPathSum,
calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x + 1, n) +
CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
maxPathSum = max(maxPathSum,
calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x, n) +
CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
maxPathSum = max(maxPathSum,
calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x + 1, n) +
CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
maxPathSum = max(maxPathSum,
calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x, n) +
CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
pathSumDP[path1x][path1y][path2x] = maxPathSum;
return maxPathSum;
}
int main() {
int n = 3;
int mat[n][row] = {
{ 1, 2, 4 },
{ 3, 0, 1 },
{ 5, −1, −1 }
};
cout<<"矩阵从顶部到底部再到顶部的最大和路径为 "<<calcMaxPathSumOfMat(mat, 0, 0, 0, n);
return 0;
}输出结果
矩阵从顶部到底部再到顶部的最大和路径为 15