C ++中倒三角形的最大路径总和

在这个问题上，我们以倒三角形的形式给出数字。我们的任务是创建一个程序，该程序将在倒三角形中找到最大路径总和。

数字的倒三角形式是当第一行包含n个元素，第二个n-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