具有最大平均值的 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 和其他语言)编写相同的程序。我们希望您觉得本教程有用。