最大平均値を持つC++パス

この問題で2D行列が与えられ、最大平均値を持つパスを見つける必要があります。パスの場合、ソースは左上のセルで、宛先は右下のセルです（例：-

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はコストマトリックスの次数です。したがって、最大パスの合計を計算する必要があります。さて、これは古典的なdp問題の1つであり、それを使用して解決し、結果を出力します。

結論

このチュートリアルでは、問題を解決して、平均値が最大のパスを見つけます。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（Normal）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。