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

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

역삼각형 숫자 형식은 첫 번째 행에 n개의 요소, 두 번째 n-1개 등의 요소가 포함된 배열입니다.

여기서 우리는 각 행에서 하나의 요소를 추가하여 얻을 수 있는 최대 합 3을 찾아야 합니다.

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

입력 -

5 1 9
 3 6
  2

출력 − 17

설명 − 여기에서 경로의 가능한 최대 요소를 고려하여 마지막 행에서 맨 위 행까지의 경로를 찾았습니다.

이 문제를 해결하기 위해 최소 비용 경로 문제의 경우에 적용하는 것과 유사한 동적 프로그래밍 접근 방식을 사용할 것입니다. 여기에서 우리는 바닥에서 시작하여 최대 합을 제공하는 경로를 찾을 것입니다.

이 전에 우리는 왼쪽의 모든 수를 이동하고 나머지 자리에 0을 추가하여 역삼각형을 일반 행렬로 간주할 것입니다.

예시

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

#include <iostream>
using namespace std;
#define N 3
int findMaxPathSumInvertedTriangle(int matrix[][N]){
   int maxSum = 0;
   for (int i = N - 2; i >= 0; i--) {
      for (int j = 0; j < N - i; j++) {
         if (j - 1 >= 0)
            matrix[i][j] += max(matrix[i + 1][j], matrix[i + 1][j - 1]);
         else
            matrix[i][j] += matrix[i + 1][j];
            maxSum = max(maxSum, matrix[i][j]);
      }
   }
   return maxSum;
}
int main(){
   int invertedTriangle[N][N] = {
      {5, 1, 9},
      {3, 6, 0},
      {2, 0, 0}};
   cout<<"The maximum path sum is "<<findMaxPathSumInvertedTriangle(invertedTriangle);
   return 0;
}

출력

The maximum path sum is 17