具有最大平均值的 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){ //我们的函数返回最大平均值
int dp[n+1][n+1];
dp[0][0] = cost[0][0];
for (int i = 1; i < n; i++) //初始化dp矩阵的第一列
dp[i][0] = dp[i-1][0] + cost[i][0];
for (int j = 1; j < n; j++) //初始化dp矩阵的第一行
dp[0][j] = dp[0][j-1] + cost[0][j];
for (int i = 1; i < n; i++) //构建我们矩阵的其余部分
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]; //现在我们将最大路径和除以移动次数
}
int main(){
int cost[3][3] = { {1, 2, 3}, {4, 5, 6},{7, 8, 9}};//给定网格
int n = 3; //我们矩阵的顺序
printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1)));
return 0;
}输出结果5.8
以上代码说明
在上述方法中，我们观察到我们采取的最大移动等于(2*n)-1，其中n是成本矩阵的阶数，因为我们现在有一个固定的分母。因此，我们需要计算最大路径和。现在，这是经典的dp问题之一，我们使用它来解决它，然后我们打印我们的结果。
结论
在本教程中，我们解决了一个问题，以找到具有最大平均值的Path。我们还学习了针对此问题的C++程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。我们希望本教程对您有所帮助。