C++에서 삼각형의 최대 경로 합

이 문제에서는 삼각형 형태의 숫자가 제공됩니다. 우리의 임무는 삼각형에서 최대 경로 합을 찾는 프로그램을 만드는 것입니다.

요소는 첫 번째 행에서 1개의 요소로 시작하여 n번째 행에 요소가 있을 때까지 요소 수가 증가하는 다음 행으로 정렬됩니다.

따라서 프로그램은 삼각형 요소의 최대 합을 제공하는 경로를 찾습니다. 따라서 최대 합계를 제공하는 경로를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다. −

입력 -

  1
 5 6
8 2 9

출력 − 16

설명 -

상단에서 경로는 최대 합계를 반환합니다 - 9+6+1 =16

이 문제를 해결하기 위해 상향식 접근 방식을 사용하는 동적 프로그래밍을 사용할 것입니다.

이를 위해 먼저 삼각형의 모든 숫자를 왼쪽으로 이동하고 끝에 0을 추가합니다. 이렇게 하면 삼각형이 최소 비용 경로 문제에서 보는 것과 유사한 행렬처럼 보입니다. 그런 다음 맨 아래에서 시작하여 각 요소에 대해 가능한 모든 경로를 확인하고 해당 요소까지 가능한 최대 합계를 제공하는 경로를 선택합니다. 그리고 삼각형에서 경로의 가능한 최대 합을 찾기 위해 비슷한 방식으로 맨 위로 이동합니다.

예시

삼각형에서 최대 경로 합을 찾는 프로그램 -

#include<iostream>
using namespace std;
#define N 3
int findMaxPathSumTriangle(int mat[][N], int m, int n){
   for (int i=m-1; i>=0; i--){
      for (int j=0; j<=i; j++){
         if (mat[i+1][j] > mat[i+1][j+1])
            mat[i][j] += mat[i+1][j];
         else
            mat[i][j] += mat[i+1][j+1];
      }
   }
   return mat[0][0];
}
int main() {
   int triangle[N][N] = {
      {1, 0, 0},
      {5, 6, 0},
      {8, 2, 9} };
   cout<<"The maximum path sum in triangle is "<<findMaxPathSumTriangle(triangle, 2, 2);
   return 0;
}

출력

The maximum path sum in triangle is 16