面试算法-91-不同的二叉搜索树

题目

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

示例 1：

输入：n = 3
输出：5

分析

动态规划：
1、状态定义：dp[i]为当有i个节点时，一共可以组成的二叉搜索树数目
2、状态转移：dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]（dp[3]：代表一共3个节点，则左右树一共有2个节点）

解

class Solution {
    // 1 -> 1
    // 2 -> 2
    // 3 -> 5
    // 4 -> 14
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16