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