julyedu 从暴力递归走向动态规划——研究过卡特兰数的同学欢迎进来
本人最近刷了一些的dp的题目。其中一些题目，它们拥有相似甚至相同的算法框架，其思路都是利用**卡特兰数**的性质来解决。本人稍微总结了一下一些经验，希望帮助大家更高效的刷题，并少走弯路。如果你有更好的解法，欢迎进行探讨。
卡特兰数的定义
卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790......
递推公式
其递推公式为: $$ f(n)= f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0) (n>=2) $$
卡特兰数的应用
1、 n对括号正确匹配数目
给定n对括号，求括号正确配对的字符串数，例如：
0对括号：[空序列] 1种可能
1对括号：() 1种可能
2对括号：()() 、(()) 2种可能
3对括号：((()))、 ()(())、 ()()()、 (())()、 (()()) 5种可能
2、凸多边形的三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是输入凸多边形的边数n，输出不同划分的方案数f(n)
n=0,1,2，均不能组成多边形，故而f(0)=f(1)=f(2)=0
n=3, 本身就是三角形，无需划分，故而f(3)=1
n=4, 考虑矩形，正反对角线，显然f(4)=2
n=5，五边形，一共五种，f(5)=5，如下图所示：
n=6， 六边形，一共14种，f(6)=14，如下图所示：
3、给定节点组成二叉搜索树
给定N个节点，能构成多少种不同的二叉搜索树？
n=0，规定空树也是一颗BST，故f(0)=1
n=1，显然f(1)=1
n=2，f(2)=2，如下图所示：
n=3，f(3)=5，如下图所示：
另外还有出栈顺序，排队找零问题等等，有兴趣的同学可以查阅相关资料