【LeetCode動態規劃#04】不同的二元搜尋樹（找規律，有點像智力題）
不同的二元搜尋樹
給定一個整數 n，求以 1 ... n 為節點組成的二元搜尋樹有多少種？
範例:
思路
題意分析
先找一下關係
當n = 1時，如果元素就是1，以1為頭節點
1
當n = 2時，分別以1和2為頭節點
1 2
/ \
2 1
然後當n = 3時的情況就是範例中給的那幾種
找找有什麼規律
當n = 3且使用1為頭節點時，其右子樹的佈局和n = 2時的佈局是一樣的（注意看1-2、2-1和3-2、2-3的方向，是不是一樣的，數值不同沒有影響）
當n = 3且使用2為頭節點時，其左右子樹佈局和n = 1時的佈局是一樣的（n = 1是左右子樹為空，也算1種情況）
當n = 3且使用3為頭節點時，其左子樹的佈局和n = 2時的佈局是一樣的
某種程度上，n = 3的二元搜尋樹種類情況可以由n = 2以及n = 1推匯出來
因此，n = 3時，二元搜尋樹種類 = 頭節點為1時的情況+頭節點為2時的情況+頭節點為3時的情況，來組成
即,頭1+頭2+頭3
公式描述
接下來分析不同頭節點時的情況
從圖中可以看出，頭節點為1時有：
1 1
\ \
3 2
/ \
2 3
頭節點為1時有多少種二元搜尋樹可以用以下公式描述：
頭1 = 左子樹有0個節點時有幾種二元搜尋樹 * 右子樹有2個節點時有幾種二元搜尋樹；（2種）
如何理解？
頭節點為1來構建二元搜尋樹的話，如果左子樹只給0個節點，那麼左子樹的型別就只有1種（也就是空）；然後給右子樹2個節點的話，那麼右子樹就可以有3-2和2-3兩種情況。
左右子樹的情況組合在一起就得到以下結論：
當n = 3時，使用1作為頭節點可以構建2種（1*2）不同的二元搜尋樹
還不理解再舉個例子：
10 / \ 5個節點 10個節點上述以10（數值無所謂）為頭節點的二元樹，其左右子節點的情況如上
那麼，可以構成的二元樹的種類一共是：5*10種
同理可以得到頭2、頭3的公式描述：
頭2 = 左子樹有1個節點時有幾種二元搜尋樹 * 右子樹有1個節點時有幾種二元搜尋樹；（1種）
頭3 = 左子樹有2個節點時有幾種二元搜尋樹 * 右子樹有0個節點時有幾種二元搜尋樹；（2種）
與範例對照的話發現是可以對上的
還是先來五部曲吧
五步走
1、確定dp陣列的含義
根據題目所求可以得到
dp[i]:輸入為i時有dp[i]種不同的二元搜尋樹
2、確定遞推公式
由前面的分析可以知道，當輸入n為3時，可以組成的二元搜尋樹種類（也就是dp[3]）是有分別使用1、2、3作為頭節點時產生的種類相加得到的。
即，
dp[3] = 頭1+頭2+頭3
dp[3] = dp[0]dp[2] + dp[1]dp[1] + dp[2]dp[0];
明確了上述問題後可以開始討論dp[i]
dp[i]可以從哪裡求出來？
那肯定是由以1、2、3...i為頭節點的所有情況相加得出，於是我們需要列舉所有頭節點情況
以 j 來代表頭節點數，那麼該二元搜尋樹的左子樹有多少個節點？答案是 j-1 個
（舉個例子來理解：範例中以3為頭節點時，其左子樹是不是有兩個節點）
那麼該二元搜尋樹的右子樹有多少個節點？答案是 i-j 個
因為我們這裡是二元搜尋樹，現在以i為頭節點了，右子樹的節點值一定都比 i 大，總節點數是 i ，那麼留給右子樹的節點數就是i-j了
套用dp陣列的定義：
輸入為 j-1 時有 dp[j-1] 種不同的二元搜尋樹；
輸入為 i-j 時有 dp[i-j] 種不同的二元搜尋樹；
那麼dp[i]怎麼求？
根據 公式描述 中的討論可得：dp[i] = dp[j-1] * dp[i-j];（只是當前j下的dp[i]）
因為 j 是代表遍歷所有頭節點的情況，所以要把頭節點為1~i的情況都相加才能得出最後的dp[i]
即遞推公式應該是：dp[i] += dp[j-1] * dp[i-j];（i個節點有多少種不同的二元搜尋樹）
怎麼理解？
拿前面的例子dp[3]來說
dp[3] = dp[0]dp[2] + dp[1]dp[1] + dp[2]dp[0];
此處j的遍歷範圍是1~i，可以寫成以下形式
dp[3] = dp[1-1]dp[3-1] + dp[2-1]dp[3-2] + dp[3-1]dp[3-3];
3、確定初始化方式
前面的討論也說了dp[0]、dp[1] (即，n=0、n=1)可以用於推出後續情況
那麼就要對這兩者進行初始化嗎？其實只需要初始化dp[0]就行了，dp[1]也可以通過dp[0]推出
dp[0]的含義是什麼？輸入的i是0，0個節點有多少種不同的二元搜尋樹呢？答案是1個，因為空二元樹也是一種二元搜尋樹
所以dp[0] = 1；
並且這也符合遞推公式的要求，因為如果有空節點，其種類如果是0，那麼不論後面的其他子樹有幾種情況，結果都是0，就沒有意義了，因此空節點的種類應該是1（如果左右子樹都空的話，也就是1*1=1，遞推還能繼續進行下去）
4、確定遍歷順序
還是從dp[3]來看
dp[3] = dp[0]dp[2] + dp[1]dp[1] + dp[2]dp[0];
dp[3]都是由小於3的狀態累加推導來的，所以就要從小到大遍歷，才可以利用之前遍歷的狀態
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
dp[i] += dp[j-1] * dp[i-j];
}
}
程式碼
class Solution {
public:
int numTrees(int n) {
//定義dp陣列
vector<int> dp(n + 1);
//初始化dp陣列
dp[0] = 1;
//dp[1] = 1;//不用初始化dp[1]，否則按理來說dp[1]應該是1，手動初始化會使其變為2
//遍歷
for(int i = 1; i <= n; ++i){//此處i確實要取3，所以有等於號
for(int j = 1; j <= i; ++j){
dp[i] += dp[j - 1] * dp[i - j];
}
}
// cout << dp[1]<< endl;//列印dp陣列debug
return dp[n];//確實要返回n的dp而不是n-1
}
};
ps：真難啊動態規劃