資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法學用 C++ 生成唯一的二叉搜尋樹
假如我們有一個整數 n，我們需要計算所有結構上唯一的二叉搜尋樹，這些樹從中儲存 1 到 n 的值。所以如果輸入是 3，那麼輸出將是 5，因為這些樹為 -
為此，我們將按照以下步驟進行操作 -
- 建立一個大小為 n + 1 的陣列
- dp[0] := 1
- 對於 i := 1 到 n
- 對於 j := 0 到 i - 1
- dp[i] := dp[i] + (dp[i - 1 - j] * dp[j])
- 對於 j := 0 到 i - 1
- 返回 dp[n]
示例（C++）
讓我們看看以下實現以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numTrees(int n) {
vector <int> dp(n+1);
dp[0] = 1;
for(int i =1;i<=n;i++){
for(int j = 0;j<i;j++){
//cout << j << " " << i-1-j << " " << j << endl;
dp[i] += (dp[i-1-j] * dp[j]);
}
}
return dp[n];
}
};
main(){
Solution ob;
cout << ob.numTrees(4);
}輸入
4
輸出
14
更新於:2020 年 4 月 28 日
146 次瀏覽
廣告