1
2

输入：n = 3
输出：5

1
2

输入：n = 1
输出：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设 dp[i]: 整数[1..=i]组成的不同二叉搜索树数;
    /// 2. 设 f[i]: 以i为根节点的以[1..=i]组成的不同二叉搜索树数;
    /// 3. 则 dp[i] = f[1] + f[2] + .. + f[i];
    ///      f[i] = dp[i-1] * dp[n-i]
    ///    故 dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + .. + dp[n-1]*dp[0]
    ///
    pub fn num_trees(n: i32) -> i32 {
        if n == 1 {
            return 1;
        }
        let n = n as usize;
        let mut dp = vec![0_i32; n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for i in 2..=n {
            for j in 1..=i {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        dp[n]
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    /*
    ## 解题思路
    * 动态规划
      G(n):  n个节点二叉排序树的个数
      f(i): 为以i为根的二叉搜索树的个数，
      则
           G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
      当i为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
           f(i) = G(i-1) * G(n-i)
       综合得到 卡特兰数 公式
           G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)

    */
    int numTrees(int n) {
        if (n==1) return 1;
        vector<int> g(n+1);
        g[0] = 1;
        g[1] = 1;
        for (int i=2; i<=n; ++i) {
            for (int j=1; j<=i; ++j) {
                g[i] += g[j-1]*g[i-j];
            }
        }

        return g[n];
    }
};