WEI-CHENG CHEN

說明

給定一個整數 n，代表節點數為 1 到 n，請問可以組成多少種不同的 二叉搜尋樹（BST）？

BST：左邊的值 < 根節點 < 右邊的值

解法：用 DP 去解

卡塔蘭數(Catalan Number)：以每個數字作為根節點時，左子樹與右子樹的組合數相乘，然後全部加總起來。

• dp[i]表示有 i 個節點時，可以組成的 BST 總數
• 對於每個 j(1 到 i)，假設 j 是跟節點：
  • 左子樹有 j-1 個節點
  • 右子樹有 i-j 個節點
• 假設節點[1,2,3,4]，且根結點為 2
  • 左子樹為 1 => 就是 j-1 = 2-1 = 1
  • 右子樹為 [3,4] = 2 = i-j = 4-2
• 公式：dp[i] += dp[j - 1] * dp[i - j];

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+1;i++){
            for(int j=1;j<i+1;j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
};