Leetcode Unique BST

題目

給定正數n，計算1到n組成不同的BST的個數。

題目分析

BST的特點是

左子樹小于根

,

右子樹大于根

，這是一個遞歸的定義。是以我們也可以采用遞歸的反方向，自下而上的遞推出不同BST的個數。首先計算1個結點的BST個數，接下來計算2個，3個，……直到計算完n個結點。

建立兩個數組，

cnt[i]

和

dp[i][j]

，

cnt[i]

表示i個結點能夠組成不同的BST的個數，

dp[i][j]

表示給出i個結點，以j為根組成不同的BST的個數。因為二分搜尋樹用inorder周遊出來的數組是遞增的，是以我們利用這一特性，可以直到給出結點

i~n

作為一棵子樹時，這棵子樹具有cnt[n - i]個不同的BST樹。此外，因為子樹可能為空，是以我們取左子樹、右子樹、兩者相乘數量上的最大值。根據該思路寫出狀态轉移方程：

dp(i,j)={0,max(cnt[i−j],cnt[j−1],cnt[i−j]∗cnt[j−1]),i < j0≤j≥i

初始化

cnt[1] = 1
dp[1][1] = 1
           

源代碼

class Solution {
public:
    int numTrees(int n) {
        int cnt[n + ];
        int dp[n + ][n + ];
        memset(cnt, , sizeof(cnt));
        memset(dp, , sizeof(dp));
        cnt[] = ;
        dp[][] = ;
        for (int i = ; i <= n; i++) {
            for (int j = ; j <= i; j++) {
                dp[i][j] = max(max(cnt[i - j], cnt[j - ]), cnt[i - j] * cnt[j - ]);
                cnt[i] += dp[i][j];
            }
            cout << cnt[i] << endl;
        }
        return cnt[n];
    }
};