数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究以 C++ 计算反向三角形的最大路径和
在这个问题中，我们得到了一个反向三角形形状的数字。我们的任务是编写一个程序，它将找到反向三角形的最大路径和。
反向三角形形态的数字是一种排列方式，其中第一行包含 n 个元素，第二行包含 n-1 个元素，依此类推。
在这里，我们必须通过从每一行添加一个元素中得到最大和。
我们通过一个例子来理解这个问题 −
输入 −
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
更新于：03-6 月-2020
122 次浏览
广告