具有最大平均值的 C++ 路径
在这个问题中给定一个二维矩阵，我们需要找到具有最大平均值的路径。对于路径，我们的源是最左上角的单元格，目标是最右下角的单元格，例如 -
Input : Matrix = [1, 2, 34, 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 和其他语言。我们希望本教程对您有所帮助。
以上是 具有最大平均值的 C++ 路径 的全部内容， 来源链接： utcz.com/z/327416.html
