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

題意：給定一個數(shù)字n，那么用從1到n這些數(shù)字構(gòu)造一個二叉查找樹有多少種方法？

思路：
自己開始想的是用搜索的方法，即從1到n，嘗試以每個數(shù)字都作為根節(jié)點去構(gòu)造一個二叉查找樹，需要用一個數(shù)組來記錄當(dāng)前使用了哪些數(shù)字。但是有一個很難處理的地方是需要記錄當(dāng)前這棵樹的狀態(tài)，這樣才能確定當(dāng)前搜索到的數(shù)字有幾種放置的方法。想了一下，這種搜索的方法時間復(fù)雜度非常高，應(yīng)該是階乘的級別。
最后想到應(yīng)該是動態(tài)規(guī)劃的思路，但是沒想出來解法，還是看了discuss的答案。n個數(shù)字情況下，從1到n每個數(shù)字都可以當(dāng)做根節(jié)點，用g(k,n)表示n個數(shù)字，以k為根節(jié)點生成一個BST的方案個數(shù)，用t(n)表示n個數(shù)字生成BST的總方案數(shù)，則t(n) = g(1,n) + g(2,n) + ... + g(n,n)，容易知道t(1) = 1,t(2) = 2。
假如n=4，k=2，則k的左子樹只能由1來構(gòu)造，右子樹由3、4來構(gòu)造，而用3、4構(gòu)造和用1、2構(gòu)造的方案數(shù)其實是一樣的，所以能夠得出g(2,4) = t(1) * t(2)，即g(k, n) = t(k-1) * t(n-k)，由此能夠推出t(n) = t(0) * t(n-1) + t(1) * t(n-2) + ... + t(n-1) * t(0)，t(0)可設(shè)置為1.

public int numTrees(int n) {
    if (n <= 1) {
        return 1;
    }

    int[] nums = new int[n+1];
    nums[0] = 1;
    nums[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            nums[i] += nums[j - 1] * nums[i - j];
        }
    }

    return nums[n];
}