최대 평균값이 있는 C++ 경로

이 문제에서 2차원 행렬이 주어지면 최대 평균값을 갖는 경로를 찾아야 합니다. 경로의 경우 소스는 맨 위 왼쪽 셀이고 대상은 맨 아래 오른쪽 셀입니다(예:−

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 문제 중 하나이며 이를 사용하여 해결한 다음 결과를 인쇄합니다.

결론

이 튜토리얼에서는 평균값이 최대인 경로를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결한 완전한 접근 방식( Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.