96. Unique Binary Search Trees

目标 G(n) = 以 1-n 每一个数字为根 F(1,n) + F(2,n) + F(3,n) …. + F(n,n) F(i,n) = G(i-1) * G(n-i) 左右子树种数相乘 （和是 n-1 代表除了根节点的节点个数）

这个式子还能求卡特兰数

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) {
            dp[i]+=dp[j-1]*dp[i-j];
        }
    }

    return dp[n];
}

卡特兰数

递推序列特征 n = 0: 1 n = 1: 1 n = 2: 2 n = 3: 5 n = 4: 14 n = 5: 42 n = 6: 132

本质上都可以等价到出入栈问题上 1）出栈次序问题

• n个数有多少种不同的进出栈顺序？
  • n辆火车有多少种不同进出站顺序？

2）加括号问题

• n对括号有多少种匹配方式？
  • n+1个数相乘，有多少种乘法顺序？（要加n对括号）

3）二叉树问题

• 给定n个节点，能构成多少种不同的二叉树？
  • 已知二叉树的前序，求所有可能的中序遍历有多少种？

4）排队顺序问题

• 有2n个人排成一行进入剧场。入场费5元。其中n个人只有5元钞票，n个人只有10元钞票（必须找零），剧院无其它钞票，问有多少种买票顺序能让每个人都顺利买票（其实就是一个括号匹配问题）

#math