数据结构
网络
关系型数据库管理系统
操作系统
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次浏览
广告