given n, how many structurally unique bst‘s (binary search trees) that store values 1...n?for example,given n = 3, there are a total of 5 unique bst‘s.
首先，需要明确binary search tree的定義。這裡引用一下。
另外，需要明确什麼是structurally unique。這裡按照我的了解，應該是指兩個bst之間的關系,structurally unique可以這麼遞歸定義，兩個bst均從根起，根節點不同或者對應的左子樹或右子樹structurally unique.
聯想得到的一些結論：
二叉樹-由于結構的特殊性，常使用遞歸的方法解決問題，分而治之。
二分查找樹-由于二分查找樹本身的有序性，可以考慮是否通過周遊不同結構的bst可能會得到不同的序列，通過查找不同序列的數目來确定bst不同結構的數目。通過驗證n=3，發現這種思路不可行，已經可以排除這種情況。
演繹推理：
首先，考慮如何從特殊、小規模情況分析獲得規律。設num代表unique bst的數目。
n=1,num=1
n=2,num=2
n=3,num=5
這裡特别觀察了一下題目中給出了圖檔的n=3的情況，發現根節點出現過1,2,3，考慮是否可以通過分析1~n分别為root的時候num的值，得到它們的累加和即為結果。
結合聯想中提到的分而治之的用法，如果我選取了一個j(1 < j < n)作為root，根據bst的定義，1～j-1一定是在左子樹上，j+1~n一定是在右子樹上，問題可以分解為，得到左、右子樹的不同結構數目，它們的乘積就是標明j的時候，num的值。這是依據排列組合的乘法原理。
同時我們考慮分而治之的方法，結合上面的分析，我們要求num值，即需要求對1～n中每一個值j作為root，1～j-1的num和j+1~n的num的乘積，這就将問題劃分為了更小的規模。
遞歸處理問題的時候，一定需要注意邊界條件。在這裡先統一假設已經确定了某一個j作為root。假設左子樹隻有一個元素的時候，可得左子樹的num=1，倘若左子樹為空，這個時候對應的左子樹num值應該是沒有意義的，設右子樹num=k(k>0),這個時候對應的總num應該是k，我們可以通過檢查某個子樹為空時，進行特殊的判斷，取另外的不為空的子樹的num值作為總num值，我們也可以巧妙地給空子樹設定一個num=1的值，讓這種情況也可以通過乘法定理計算出來，可以保持代碼的簡潔性和一緻性，不用再做特殊判定。
回到邊界條件的判定上來，到底什麼才是邊界條件，如何得到邊界條件。我的考慮是，首先結合目前問題，我們是将規模為1..j..n的問題，劃分為1...j-1和j+1...n，規模越來越小，最後會收縮成為子樹隻包含1個元素，最後子樹為空的情況。這個時候隻要給出子樹為空的值就可以終結整個遞歸的過程。
代碼：
感覺到這裡，已經想的差不多了，可以開始寫寫代碼。本來想直接定義一個f(n)，發覺這樣不行，因為我會将問題分解為1~j-1，j+1~n，f(n)不能代表j+1~n的情況，是以這裡我用f(lst)來定義，lst就代表一個有序數組。
代碼見此：
很不幸，這段代碼逾時了，如果我多添加一個len(lst)==1的判斷，代碼是能過的，不過耗時780ms，那麼接下來就需要分析一下這段代碼的時間複雜度以及到底還有沒有優化的空間吧。
時間複雜度分析這一塊内容暫時略過，具體可以參考算法導論第二章使用遞歸樹分析合并排序複雜度的部分。分析結果是這種做法的複雜度會是n + 2*(n -1) + 4 * (n - 2) + 8 * (n - 3)....比o(2^n)還要大，小于o(n*2^n)，怪不得如此之慢。
怎麼優化呢？看了看上面的代碼，考慮貌似num值與lst裡面具體的元素無關，隻和這個清單的長度相關，發散一下，是否是對于任何一個排好序的數組a1,a2,a3...an，它們的num值應該是相同的？考慮到bst自身的性質，也就是規定了左子樹任一節點<root<右子樹任一節點，這個結論直覺上是成立的。我這裡不太清楚嚴謹的數學證明應該怎樣給出。
這個時候，之前設函數f(n)，現在的子問題就劃分為了f(j), f(n - j -1),這裡出現了更小規模的重複子問題，一下子就聯想到了動态規劃。這裡考慮對于n的序列，不斷的将n分割成另外兩個小序列。即可以得到狀态方程f(n) = f(0) * f(n-1) + f(1) * f(n-2)+....+f(n-1)*f(0)
這個算法一看就知道是o(n^2)，還勉強可以接受吧。
再晃眼一看，這個序列看起來像是有通項公式的數組，去網上搜了一下，發現這個序列正好叫做卡特蘭數，果然有遞推公式存在
那就再來一段code吧。
由于通項公式裡面有階乘計算，是以得到了o(n)的複雜度。
這到題目就分析到這個地方，關于o(n)是否是最佳的解決方案，我并不能證明，不知道還有沒有其他牛逼的做法。