在这个问题上,我们以倒三角形的形式给出数字。我们的任务是创建一个程序,该程序将在倒三角形中找到最大路径总和。
数字的倒三角形式是当第一行包含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