資料結構
網路技術
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中的三角形
假設我們有一個三角形。我們需要找到從上到下的最小路徑和。每一步，我們都可以移動到下方行中相鄰的數字。
例如，如果以下三角形是這樣：
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
從上到下的最小路徑和為 11（2 + 3 + 5 + 1 = 11）。
讓我們看看步驟 −
建立一個表用於動態規劃方法。
n := 三角形的尺寸
對於 i := n – 2 到 0
對於 j := 0 到 i
dp[j] := triangle[i, j] + dp[j] 和 dp[j + 1] 兩者之間的最小值
返回 dp[0]
示例 (C++)
讓我們看看以下實現，以更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector <int> dp(triangle.back());
int n = triangle.size();
for(int i = n - 2; i >= 0; i--){
for(int j = 0; j <= i; j++){
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
};
main(){
Solution ob;
vector<vector<int> > v = {{2},{3,4},{6,5,7},{4,1,8,3}};
cout << ob.minimumTotal(v);
}輸入
[[2],[3,4],[6,5,7],[4,1,8,3]]
輸出
11
更新日期： 2020 年 4 月 28 日
259 次瀏覽
廣告