在这个问题上,我们得到的三角形形式的数字。我们的任务是创建一个程序,该程序将在三角形中找到最大路径总和。
元素从第一行开始排列,其中第一个元素为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