Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 96. Unique Binary Search Trees

---

題目：


方法：

選一個 i 當 root：
左子樹：[1 ... i-1] => 有 G(i-1) 種
右子樹：[i+1 ... n] => 有 G(n-i) 種

解答：

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);

        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int root = 1; root <= i; ++root) {
                dp[i] += dp[root - 1] * dp[i - root];
            }
        }

        return dp[n];
    }
};