C++의 행렬에서 마지막 행의 모든 ​​요소에서 끝나는 최대 가중치 경로

이 문제에서는 정수 n과 셀의 가중치를 포함하는 n X n 크기의 행렬이 제공됩니다. 우리의 임무는 행렬의 마지막 행의 모든 ​​요소에서 끝나는 최대 가중치 경로를 찾는 프로그램을 만드는 것입니다. 경로를 찾는 동안 순회는 왼쪽 상단(0,0)에서 시작하고 유효한 이동은 아래쪽 대각선이며 왼쪽 이동은 허용되지 않습니다.

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

입력 -

n = 3
Mat[3][3] ={
   {4, 3, 1}
   {5, 8, 9}
   {6, 7, 2}}

출력 -

19

설명 -

All paths that can be used will be
Path1: 4+5+6 = 15
Path2: 4+8+7 = 19
Path3: 4+8+2 = 12
Path4: 4+5+7 = 16

이 중에서 가능한 가장 좋은 경로는 가중치가 19인 path2입니다.

따라서 한 가지 가능한 솔루션은 모든 경로를 계산한 다음 비교할 수 있지만 n이 큰 경우 비효율적인 접근 방식이 됩니다.

효과적인 솔루션은 일종의 중첩 문제이므로 동적 프로그래밍을 사용하는 것입니다. 루트에서 시작하여 원하는 결과를 제공할 수 있는 n개의 가지입니다.

우리는 행렬의 해당 셀에 도달하기 위해 통과하는 주어진 경로의 최대 가중치를 저장할 행렬을 생성합니다.

이것은 행렬의 마지막 행의 최대 합이 되도록 하고 인쇄합니다.

예시

문제를 해결하는 프로그램,

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int maxCost(int matrix[][MAX], int N) {
   int sumMat[N][N];
   memset(sumMat, 0, sizeof(sumMat));
   int maxSum = 0;
   sumMat[0][0] = matrix[0][0];
   for (int i=1; i<N; i++)
      sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
   for (int i=1; i<N; i++)
   for (int j=1; j<i+1&&j<N; j++)
      sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
   for (int i=0; i<N; i++)
      if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
      return maxSum;
}
int main(){
   int mat[MAX][MAX] ={
      {5 , 6 , 1 },
      {2 , 11 , 10 },
      {15, 3 , 2 }};
   int N = 3;
   cout<<"Maximum Path Sum for top-left cell to last row is : "<<maxCost(mat, N)<<endl;
   return 0;
}

출력

Maximum Path Sum for top-left cell to last row is : 22