例题一



F（1） = 2 F（2） = 4 F(3) = 7

状态转移方程 ：F(N) = F（N-1） + n ；

卡特兰数

参考连接（C++卡特兰数_卡特兰数c++最省时间的算法_SkeletonKing233的博客-CSDN博客）

前几项分别是

1 ， 2 ，5 ， 14 ， 42 ， 132 ， 429 ， 1430 ， 4862 ；

初始值：f(0) = f(1) = 1递推公式：f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + …… + f(n - 1) * f(0)

常解决问题

括号化：P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？（答案：catalan[n]）出栈次序：一个栈的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?（答案：catalan[n]）凸多边形三角划分：在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形，共有多少种不同的分法？（答案：catalan[n - 2]）给定节点组成二叉搜索树：给定N个节点，能构成多少种不同的二叉搜索树？（答案：catalan[n]）n对括号正确匹配数目：给定n对括号，括号正确配对的字符串数是多少？（答案：catalan[n]）

int catalan(int n){

    if (n == 1)return 1;
    if (n == 2)return 1;
    int res = 0 ;
    for (int i = 1; i <= n - 1;i++){
        res += catalan(i)*catalan(n - i);
    }
    return res;

}