C++에서 위에서 아래로 행렬의 최대 합 경로

문제 설명

n*n 행렬을 고려하십시오. 행렬의 각 셀에 할당된 값이 있다고 가정합니다. i행의 각 셀에서 i+1행의 대각선으로 더 높은 셀로만 이동할 수 있습니다[즉, cell(i, j)에서 cell(i+1, j-1) 및 cell(i+1, j+1) 오직]. 최대 합이 얻어지도록 위에서 언급한 조건에 따라 맨 위 행에서 맨 아래 행까지의 경로를 찾습니다.

예시

If given input is:
{
   {5, 6, 1, 17},
   {-2, 10, 8, -1},
   { 3, -7, -9, 4},
   {12, -4, 2, 2}
}

최대 합은 (17 + 8 + 4 + 2) =31

알고리즘

• 아이디어는 최대 합계 또는 첫 번째 행의 모든 ​​셀에서 시작하는 모든 경로를 찾고 마지막으로 첫 번째 행의 모든 ​​값의 최대값을 반환하는 것입니다.

• 많은 하위 문제의 결과가 계속해서 필요하기 때문에 동적 프로그래밍을 사용합니다.

예시

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int getMaxMatrixSum(int mat[SIZE][SIZE], int n){
   if (n == 1) {
      return mat[0][0];
   }
   int dp[n][n];
   int maxSum = INT_MIN, max;
   for (int j = 0; j < n; j++) {
      dp[n - 1][j] = mat[n - 1][j];
   }
   for (int i = n - 2; i >= 0; i--) {
      for (int j = 0; j < n; j++) {
         max = INT_MIN;
         if (((j - 1) >= 0) && (max < dp[i + 1][j - 1])) {
            max = dp[i + 1][j - 1];
         }
         if (((j + 1) < n) && (max < dp[i + 1][j + 1])) {
            max = dp[i + 1][j + 1];
         }
         dp[i][j] = mat[i][j] + max;
      }
   }
   for (int j = 0; j < n; j++) {
      if (maxSum < dp[0][j]) {
         maxSum = dp[0][j];
      }
   }
   return maxSum;
}
int main(){
   int mat[SIZE][SIZE] = {
      {5, 6, 1, 17},
      {-2, 10, 8, -1},
      {3, -7, -9, 4},
      {12, -4, 2, 2}
   };
   int n = 4;
   cout << "Maximum Sum = " << getMaxMatrixSum(mat, n) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다-

Maximum Sum = 31