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

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

元素从第一行开始排列，其中第一个元素为1，然后是下一行，其元素数量增加，直到第n行中有元素为止。

因此，程序将找到将在三角形中提供最大元素总和的路径。因此，我们必须找到将提供最大和的路径。

让我们以一个例子来了解问题-

输入-

  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