資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告