資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++路徑最大平均值
給定此問題中的一個二維矩陣，我們需要找到具有最大平均值的路徑。對於路徑，我們的源是左上角單元格，目標是右下角單元格，例如：
Input : Matrix = [1, 2, 3 4, 5, 6 7, 8, 9] Output : 5.8 Path with maximum average is, 1 -> 4 -> 7 -> 8 -> 9 Sum of the path is 29 and average is 29/5 = 5.8
在此問題中，我們僅允許向右或向下移動。這使得我們的問題變得更容易，因為我們知道我們需要向右移動N-1次，向下移動N-1次才能到達我們的目標。這是最短的有效路徑，因此我們將根據這些觀察結果制定我們的方法。
解決方法
在這種方法中，我們需要應用動態規劃來計算最大路徑和，因為分母是固定的。
示例
上述方法的C++程式碼
#include <bits/stdc++.h>
using namespace std;
int maximumPathSum(int cost[][3], int n){ // our function that return maximum average
int dp[n+1][n+1];
dp[0][0] = cost[0][0];
for (int i = 1; i < n; i++) // initializing the first column of our dp matrix
dp[i][0] = dp[i-1][0] + cost[i][0];
for (int j = 1; j < n; j++) // initializing the first row of our dp matrix
dp[0][j] = dp[0][j-1] + cost[0][j];
for (int i = 1; i < n; i++) // constructing the rest of our matrix
for (int j = 1; j <= n; j++)
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + cost[i][j];
return dp[n-1][n-1]; // now we divide the maximum path sum with the number of moves
}
int main(){
int cost[3][3] = { {1, 2, 3}, {4, 5, 6},{7, 8, 9}};// given grid
int n = 3; // order of our matrix
printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1)));
return 0;
}輸出
5.8
上述程式碼的解釋
在上述方法中，我們觀察到我們採取的最大移動次數等於（2*n）-1，其中n是我們的成本矩陣的階數，因為我們現在有一個固定的分母。因此，我們需要計算最大路徑和。現在，這是一個經典的動態規劃問題，我們使用它來解決，然後列印我們的結果。
結論
在本教程中，我們解決了一個問題，即找到具有最大平均值的路徑。我們還學習了此問題的C++程式以及我們解決此問題的完整方法（普通方法）。我們可以用其他語言（如C、Java、Python和其他語言）編寫相同的程式。希望本教程對您有所幫助。
更新於： 2021年11月25日
128次瀏覽
廣告