https://leetcode-cn.com/problems/unique-binary-search-trees/

原题

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

分析

• 设G(i)为i个节点组成且节点值从 1 到 i 互不相同的二叉搜索树个数
• 设f(i)为以i为根节点时的互不相同的二叉搜索树个数

所以G(i) = f(1) + f(2) + f(3) + … + f(i)

• f(i)的互不相同左子树个数是节点值1到i-1的互不相同的二叉搜索树的个数

所以f(i)的互不相同左子树个数为G(i-1)

• f(i)的互不相同右子树个数是节点值从i+1到n的互不相同的二叉搜索树的个数

所以f(i)的互不相同右子树个数为G(n-i)

根据笛卡尔积，得：以i为根节点的互不相同的二叉搜索树的个数是互不相同左子树个数乘以互不相同右子树个数，即f(i) = G(i-1) * G(n-i)

综上：

G(n) = f(1) + f(2) + f(3) + … + f(n)

f(i) = G(i-1) * G(n-i)

G(n) = G(0) * G(n - 1) + G(1) * G(n - 2) + … + G(n - 1) * G(0)

代码

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    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];
}