資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究三角形中最小和路徑的 C++ 實現
問題陳述
對於一個給定的數字三角形結構，找到從上至下的最小路徑總和。每一步，你都可以向下移動到下一行的相鄰數字。
示例
如果輸入為 −
5 7 3 8 1 2 9 6 4 5
則最小路徑總和為 13，如下 −
5 + 3 + 1 + 4
演算法
- 使用動態規劃的記憶化技巧
- 建立一個一維陣列用於記憶化，即記憶化
- 對於每一行 K，使用以下公式 −
memorization[i] = min( memorization[i], memorization[i+1]) + A[k][i];
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSum(vector<vector<int>> &arr) {
int memorization[arr.size()];
int n = arr.size() - 1;
for (int i = 0; i < arr[n].size(); ++i) {
memorization[i] = arr[n][i];
}
for (int i = arr.size() - 2; i >= 0; --i) {
for (int j = 0; j < arr[i + 1].size() - 1; ++j) {
memorization[j] = arr[i][j] +
min(memorization[j],
memorization[j + 1]);
}
}
return memorization[0];
}
int main() {
vector<vector<int>> arr = {
{5},
{7, 3},
{8, 1, 2},
{9, 6, 4, 5}, };
cout << "Minimum sum path = " << getMinSum(arr) << endl;
return 0;
}當你編譯並執行以上程式時，它將生成以下輸出 −
輸出
Minimum sum path = 13
更新於：20-12-2019
136 次瀏覽
廣告