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