資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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<<"The maximum sum path in a matrix from top to bottom and back is "<<calcMaxPathSumOfMat(mat, 0, 0, 0, n);
return 0;
}輸出
The maximum sum path in a matrix from top to bottom and back is 15
更新於: 2020年12月9日
216 次瀏覽
廣告