Content

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 19

Solution

1. 动态规划

Java

class Solution {
    public int numTrees(int n) {
        // 1 <= n <= 19
        // dp[i]表示包含[1,i]结点的不同二叉搜索树的个数
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int j = 0;
            while (j <= i - 1) {
                dp[i] += dp[j] * dp[i - 1 - j];
                j++;
            }
        }
        return dp[n];
    }
}