LeetCode 96. Unique Binary Search Trees [Medium] [C++] 解題筆記

這題要我們求數字 1~n 可以形成的 unique binary tree 的個數。

EX:

        Input: 3

       Output: 5
 

Explanation:
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

想法:

    Unique binary tree 的個數其實是一個卡特蘭數(Catalan numbers)的問題，n 個數所能組成的不同構 BST 個數就是n階卡特蘭數。

卡特蘭數也可以用來表示 n 組括弧可以組成的合法表示方式個數，以下是其通用公式。

回到問題，除了直接套用卡特蘭數的通用公式外，我們也可以從 BST 的遞迴結構上來下手，歸納出遞歸公式，首先定義

unique_bst(n) 為 1~n 可以構成的相異 BST 的個數，因為每個 node 都可以作為 root 產生相異的 BST，因此定義

F(i,n) 為以 i 作為 root 所能產生的相異 BST 的個數(ex: n=7,i=3, F(3,7) 表示選擇 3 為 root 的相異 BST 個數，

則可以得到 unique_bst(n) = F(1,n) + F(2,n) + ... + F(n,n) --- (1)

，即將每個 node 作為 root可以產生的相異 BST 個數加總，接著因為 BST 的遞迴結構(左子樹與右子樹也還是 BST)，因此可以發現 

F(i,n) = unique_bst(i - 1) * unique_bst(n - i) ---(2)

，例如 [1,2,"3",4,5,6,7] 將 3 作為 root 即 i = 3,n = 7 求 F(i,n)，

則左子樹[1,2]可組成的相異 BST 個數可以寫成 unique_bst(2) = unique_bst(i-1)，而右子樹[4,5,6,7]可以組成的相異 BST 個數可以寫成

unique_bst(4) = unique_bst(n - i)，因此 F(3,7) = unique_bst(2)*unique_bst(4)。

知道怎摸計算 F(i,n) 之後，將式(1)(2) 結合就可以計算出 unique_bst(n):

unique_bst(n) = unique_bst(0)*unique_bst(n-1) + unique_bst(1) + unique_bst(n-2) +...+ unique_bst(n-1)*unique_bst(0) ---(3)

最後需要注意 initial case，若只有 0 或 1 個 node 皆只能組成唯一一個 BST，因此 unique_bst(0) & unique_bst(1) 皆為 1。

而從上述推導可知，unique_bst(n) 需要先知道 unique_bst(0) ~ unique_bst(n-1)，因此可以用 DP 的方式，

從 unique_bst(0) (initial case) 依次計算到 unique_bst(n)。

完整程式碼:

class Solution {
public:
    int numTrees(int n) {
        vector<int> unique_bst(n+1,0);
        // initial case
        // 0 node and 1 node are have one bst
        unique_bst.at(0) = 1;
        unique_bst.at(1) = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                unique_bst.at(i) += unique_bst.at(j-1)*unique_bst.at(i-j);
            }
        }
        return unique_bst.at(n);
    }
};