具有最大平均值的 C++ 路径
c++server side programmingprogramming
在此问题中，给定一个 2D 矩阵，我们需要找到具有最大平均值的路径。对于路径，我们的源是最左上方的单元格，而目的地是最右下方的单元格，例如 −
输入:矩阵 = [1, 2, 3
4, 5, 6
7, 8, 9]
输出:5.8
具有最大平均值的路径为，1 -> 4 -> 7 -> 8 -> 9
路径的总和为 29，平均值为 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 问题，我们用它来解决它，然后我们打印结果。
结论
在本教程中，我们解决了一个问题，以找到具有最大平均值的路径。我们还学习了这个问题的 C++ 程序以及解决这个问题的完整方法(普通方法)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。我们希望您觉得本教程有用。
