資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中矩陣中最後一行任意元素的最大權重路徑
在這個問題中，我們給定一個整數 n 和一個大小為 n X n 的矩陣，其中包含單元格的權重。我們的任務是建立一個程式，找到以矩陣中最後一行任意元素結尾的最大權重路徑。在查詢路徑時，遍歷將從左上角 (0,0) 開始，有效移動將是向下和對角線，不允許向左移動。
讓我們舉個例子來理解這個問題，
輸入 −
n = 3
Mat[3][3] ={
{4, 3, 1}
{5, 8, 9}
{6, 7, 2}}輸出 −
19
解釋 −
All paths that can be used will be Path1: 4+5+6 = 15 Path2: 4+8+7 = 19 Path3: 4+8+2 = 12 Path4: 4+5+7 = 16
因為在這些路徑中，最佳路徑是路徑 2，權重為 19
因此，一種可能的解決方案是計算所有路徑，然後進行比較，但是當 n 為大數時，這將是一種低效的方法。
有效的解決方案將使用動態規劃，因為這是一種重疊問題。從根開始，有 n 個分支可以提供所需的結果。
我們將建立一個矩陣，用於儲存遍歷到矩陣中該單元格的給定路徑的最大權重。
我們將找出矩陣最後一行中的最大和並打印出來。
示例
解決問題的程式，
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int maxCost(int matrix[][MAX], int N) {
int sumMat[N][N];
memset(sumMat, 0, sizeof(sumMat));
int maxSum = 0;
sumMat[0][0] = matrix[0][0];
for (int i=1; i<N; i++)
sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
for (int i=1; i<N; i++)
for (int j=1; j<i+1&&j<N; j++)
sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
for (int i=0; i<N; i++)
if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
return maxSum;
}
int main(){
int mat[MAX][MAX] ={
{5 , 6 , 1 },
{2 , 11 , 10 },
{15, 3 , 2 }};
int N = 3;
cout<<"Maximum Path Sum for top-left cell to last row is : "<<maxCost(mat, N)<<endl;
return 0;
}輸出
Maximum Path Sum for top-left cell to last row is : 22
更新於: 2020年6月3日
298 次瀏覽
廣告