数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中三角形中的最大路径和
在这个问题中，我们得到的是三角形形式的数字。我们的任务是创建一个程序，找到三角形中的最大路径和。
元素从第一行开始排列，第一行有一个元素，然后是下一行，元素数量逐渐增加，直到第 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
更新于：2020-06-03
292 次浏览
广告