P0096_UniqueBinarySearchTrees.java

package yyl.leetcode.p00;

/**
 * <h3>不同的二叉搜索树</h3><br>
 * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？<br>
 * 
 * <pre>
 * 输入: 3
 * 输出: 5
 * 解释:
 * 以上的输出对应以下 5种不同结构的二叉搜索树：
 *    1         3     3      2      1
 *     \       /     /      / \      \
 *      3     2     1      1   3      2
 *     /     /       \                 \
 *    2     1         2                 3
 * </pre>
 */
public class P0096_UniqueBinarySearchTrees {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numTrees(3));
    }

    // 动态规划
    // 题目要求是“二叉搜索树”，二叉搜索树的特性是：左节点小于根节点，右节点大于根节点。
    // # 思路
    // 从序列 1...n 中取出数字 i，将该数字作为树根，剩余 i - 1 个元素可用于左子树，n - i 个元素用于右子树。
    // 因为[1,i]范围的元素都小于 i，(i,n]的元素都大于i，符合二叉搜索树的特性。，
    // 在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。
    // 可以看出，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此，可以使用动态规划来求解本题。
    // # 算法
    // 设一个数组 dp[n] 表长度为 n的序列能构成的不同二叉搜索树的个数
    // 考虑 i个节点的情况，根据 j拆分分成子树[0,j)和[j,i)
    // 1、如果确定 j位置为根节点（根节点确定）
    // 2、设左子树有L种，右子树有R种，那么组合是 L * R 种。（在根节点确定 j位置的情况： dp[i] = L * R = dp[j] * dp[i - j - 1]）
    // 3、 从 0 到 i 遍历 j (1≤j≤i) 得到转移方程： dp[i] += dp[j] * dp[i - j - 1]； (需要将每个j的结果都加起来)
    // 4、 考虑边界情况，当序列长度为 1（只有根）或为 0（空树）时，只有一种情况，即： dp[0]=1; dp[1]=1;
    // 5、遍历到i，从2 开始到n，得到 dp[n]即为最终答案
    // # 复杂度分析
    // 时间复杂度：O(n^2)，其中 n 表示二叉搜索树的节点个数。函数一共有 n 个值需要求解，每次求解需要 O(n) 的时间复杂度，因此总时间复杂度为 O(n2)。
    // 空间复杂度：O(n)，需要 O(n) 的空间存储 dp 数组。
    static class Solution {
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; ++i) {
                for (int j = 0; j < i; ++j) {
                    dp[i] += dp[j] * dp[i - j - 1];
                }
            }
            return dp[n];
        }
    }

    // 公式法
    // 卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名
    // 其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,16796...
    // 卡特兰数C[n]满足以下递推关系 C[n+1] = C[0]C[n] + C[1]C[n-1] ... C[n]C[0]
    // 卡塔兰数计算公式为：
    // C[0] = 1
    // C[n+1] = ((2(2n+1)​) / (n+2))*C[n]
    // 利用公式可以快速求解
    // 时间复杂度：O(1)
    // 空间复杂度：O(1)
    static class Solution1 {
        public int numTrees(int n) {
            long c = 1;
            for (int i = 0; i < n; i++) {
                c = ((2 * (2 * i + 1)) / (i + 2)) * c;
            }
            return (int) c;
        }
    }
}