Question

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3

Output: 5

Explanation:

Given n = 3, there are a total of 5 unique BST’s:

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

Solution

分析

这道题是根本不会，之后看到解法说使用动态规划，自己想解法，觉得dp[i]表示1-i时可以构建的二叉树数，可以发现，dp[i] dp[i-1]，dp[i]应该是在dp[i-1]时，第i个节点在i-1个节点的基础上，i出现的位置有三种情况：父结点，把i-1看做一个整体，此时bst可能数为dp[i-1];叶子节点，同样把i-1个节点看做一个整体，把i挂在整体上，也有dp[i-1]种情况；另外，位于中间节点，但一定是在根节点的右子树上，这个数我就求不出来了！没办法，只能看答案了。╮(╯▽╰)╭

这道题是明安图数(卡塔兰数)的一个例子。明安图数是组合数学中一个常在各种计数问题中出现的数列。一般项公式为

递推关系为：

也满足：

组合数学中有非常多的组合结构可以用卡塔兰数来计数。比如：

所有包含n组括号()的合法运算式的个数
n个节点组成不同构二叉树的方案数
etc

这里正好是卡塔兰数的一种应用，表示二叉树的方案数。应用它的递推关系。dp[i]表示i个节点时可以组成的不同构bst的方案数。比如i=3， $dp[3] = dp[0] dp[2] + dp[1]dp[1] + dp[3] * dp[0]$

表示当1为根节点，左子树的组合数为dp0，右子树为dp2；当2为根；当3为根，三种情况之和。

解法

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        dp[0] = dp[1] = 1;
        
        for (int i=2; i<=n; i++){
            for (int j=1; j<=i; j++)#根节点分别为：1-i
                dp[i] += dp[j-1] * dp[i-j];
        }
        
        return dp[n];
    }
};