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

入力 −

  1
 5 6
8 2 9

出力 − 16

説明 −

上からのパスは最大合計を返します− 9 + 6 + 1 =16

この問題を解決するために、ボトムアップアプローチを使用する動的計画法を使用します。

このために、最初に三角形のすべての数字を左シフトし、最後に0を追加します。これにより、三角形は最小コストパス問題で見られるものと同様の行列のように見えます。この後、下から始め、各要素について、すべての可能なパスをチェックし、その要素までの可能な最大の合計を提供するパスを選択します。同様の方法で上に移動して、三角形のパスの可能な最大合計を見つけます。

例

三角形の最大パス合計を見つけるプログラム-

#include<iostream>
using namespace std;
#define N 3
int findMaxPathSumTriangle(int mat[][N], int m, int n){
   for (int i=m-1; i>=0; i--){
      for (int j=0; j<=i; j++){
         if (mat[i+1][j] > mat[i+1][j+1])
            mat[i][j] += mat[i+1][j];
         else
            mat[i][j] += mat[i+1][j+1];
      }
   }
   return mat[0][0];
}
int main() {
   int triangle[N][N] = {
      {1, 0, 0},
      {5, 6, 0},
      {8, 2, 9} };
   cout<<"The maximum path sum in triangle is "<<findMaxPathSumTriangle(triangle, 2, 2);
   return 0;
}

出力

The maximum path sum in triangle is 16