C++の逆三角形の最大パス合計

この問題では、逆三角形の形で数字が与えられます。私たちのタスクは、逆三角形の最大パス合計を見つけるプログラムを作成することです。

逆三角形 数値の形式は、最初の行にn個の要素が含まれ、2番目の行にn-1が含まれる場合の配置です。

ここでは、各行から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