卡塔兰数能解什么题

卡塔兰数是一种组合数学中的数列，它能解决一些具有递归结构的问题，特别是与括号匹配相关的问题。以下是一些卡塔兰数能解决的常见问题：

括号匹配问题：给定n对括号，求所有有效的括号匹配组合。例如，当n=3时，有效的括号匹配组合包括"((()))"、"()()()"、"()(())"等，共有5种。
凸多边形划分问题：给定一个n边凸多边形，求将其划分为三角形的方式数。例如，当n=4时，将正方形划分为三角形的方式数为2。
二叉搜索树的个数：给定n个节点，求可以构建的二叉搜索树的个数。二叉搜索树是一种特殊的二叉树，其中左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。
出栈序列问题：给定1到n的整数序列，求可能的出栈序列的总数。在出栈序列中，每个元素按照从小到大的顺序出栈。
矩阵链相乘问题：给定一系列矩阵，求它们相乘的最佳顺序，使得乘法运算次数最少。

卡塔兰数在以上问题中都有广泛的应用，并且可以通过递推关系式或动态规划等方法求解。