来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目

给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路

我们定义 $dp(n)$ 为 $n$ 个节点时不同结构二叉搜索树的数量。 首先分情况考虑一下:

  1. 0个节点时,有1种结构的树($dp[0] = 1$)
  2. 1个节点时,有1种结构的树(1 作为根节点,左子树节点数量为0,右子树节点数量为0,即 $dp[1] = dp[0] * dp[0]。左子树的数量 乘以 右子树的数量$)
  3. 2个节点时,有2种结构的树(1作为根节点,左子树节点数量为0,右子树节点数量为1;2作为根节点,左子树节点数量为1,右子树节点数量为0。即 $dp[2] = dp[0] * dp[1] + dp[1] * dp[0]$)
  4. 所以可以推理出当有n个节点时的公式为:$dp[n] = dp[0]dp[n-1] + dp[1]dp[n-2] + … + dp[n-1]*dp[0]$

由此可见我们应该借助动态规范来完成此题。转换方程既是上面的公式。

代码

public int numTrees(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1; // 0个节点时的数量
    dp[1] = 1; // 1个节点时的数量
    for (int i = 2; i <= n; i++) {
        // 使用公式计算dp[i]的值
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    return dp[n];
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!