[leetcode]Unique Binary Search Trees @ Python

原題位址：https://oj.leetcode.com/problems/unique-binary-search-trees/

題意：

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.

1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3      

解題思路：這題從數學上講，其實是卡特蘭數。不過我們顯然不從數學上來解決這個問題。這題是求二叉樹的棵數。這裡有個解題技巧：一般來說求數量，要首先想到使用動态規劃（dp），而如果是像下一題的要求，不隻是數量，還要把所有的樹都枚舉出來，就要使用dfs（深度優先搜尋）來周遊決策樹了。

　　　　　那麼這道題是使用動态規劃來解決的。那麼如何去求這個問題的狀态轉移方程呢？其實大部分動态規劃的難點都是求狀态轉移方程。n=0時，為空樹，那麼dp[0]=1; n=1時，顯然也是1，dp[1]=1；n=2時，dp[2]=2; 對于n>2時，dp[n]=dp[0]*dp[n-1]+dp[1]*dp[n-2]+......+dp[n-1]*dp[0]；這不就是卡特蘭數的定義嗎？程式設計很容易實作。

代碼：

class Solution:
    # @return an integer
    def numTrees(self, n):
        dp = [1, 1, 2]
        if n <= 2:
            return dp[n]
        else:
            dp += [0 for i in range(n-2)]
            for i in range(3, n + 1):
                for j in range(1, i+1):
                    dp[i] += dp[j-1] * dp[i-j]
            return dp[n]