不同的二叉搜索树96

---

tags:

• 动态规划
• 树
• 二叉树
• 数学

---

地址：https://leetcode.cn/problems/unique-binary-search-trees/

题干

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

思路

本题可以用DP做，捷径为卡特兰数。

卡特兰数公式：

$$C_n = \frac{1}{n+1} \binom{2n}{n}$$

DP: 定义dp[i]表示i个节点能组成的二叉搜索树的个数。对于dp[i]，我们可以枚举根节点j（1到i），那么左子树有j-1个节点，右子树有i-j个节点，左子树的种数为dp[j-1]，右子树的种数为dp[i-j]，所以以j为根的种数为dp[j-1] * dp[i-j]。对所有j求和得到dp[i]。

题解

卡特兰数:

class Solution {
public:
long long combination(int n, int k) {
    if (k > n - k) k = n - k;
    long long res = 1;
    for (int i = 1; i <= k; ++i) {
        res = res * (n - k + i) / i;  // 边乘边除，保证整数
    }
    return res;
}

int numTrees(int n) {
    return combination(2 * n, n) / (n + 1);
}
    
};

DP（常规）：

class Solution {
public:
int numTrees(int n) {
    vector<int> ans(n+1,0);
    ans[0] = 1;
    ans[1] = 1;
    for(int i = 2;i<=n;++i){
        for(int j = 1;j<=i;++j){
            ans[i]+=ans[j-1]*ans[i-j];
        }
    }
    return ans[n];
}
    
};