先來看下題目
https://leetcode.com/problems/unique-binary-search-trees/
這題一般來說可以用DP解
我就是一個不會寫DP的人，觀察了下感覺是可以用遞迴之類的解
於是想破了腦看了很久才看出了些端倪
這邊引用維基百科：Catalan number
把下一次要新增的Node Leaf看成半月形節點
如果從root 進行BFS由左而右Traverse一次，會發現到最後一個leaf半月形前，內部節點數量始終會大於等於可能新增的leaf節點數量
所以這個題目可以等價於高中排列組合題目，一路領先
那種很像階題有格子、問最後有幾種走法的題目。
像是上面那個圖可以看成3個圓形、三個半月型的一路領先的題目
以前老師只有教我們直接在格子加，但其實這有公式解的
詳細的proof可以看這篇卡特蘭，我就懶得推了XD
把公式變成code會長成這樣，其實還蠻好懂得XD，如果知道這是Catalan Tree又知道這公式應該很快就解完了，不會像我看了一個多小時…XD
|
1 2 3 4 5 6 7 8 9 10 |
class Solution { public: int numTrees(int n) { long count = 1; for (long i = 1; i <= n; i++) { count = count * (i + n) / i; } return (int)(count / (n+1)); } }; |
