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