卡特兰数问题-LeetCode 96（卡特兰数，BST的构成，圆内连弦）

卡特兰数问题：LeetCode #96

1

编程题

卡特兰数简介

卡特兰（Catalan）数来源于卡特兰解决凸n+2边形的剖分时得到的数列Cn，在数学竞赛、信息学竞赛、组合数学、计算机编程等方面都会有其不同侧面的介绍．卡特兰问题的解决过程应用了大量的映射方法，堪称计数的映射方法的典范．

假设h(0) = 1, h(1) = 1, 则卡特兰数满足以下递推式： h(n) = h(n-1) * (4 * n-2)/(n+1)----十分重要的递推式

【LeetCode #96】不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

解题思路：

由于题目是不同的二叉搜索树，那么就与每个节点的值无关了，只考虑构成二叉树的结构问题！

思路一：使用动态规划算法，假设有i个节点构成二叉树，以根节点分割，左子树有j个节点，则： dp[i] = dp[j] * dp[i-j-1] 其中dp[i]表示节点总数为i时可以有多少种方案，就等于左子树的方案数*右子树的方案数 思路二：使用卡特兰数递推式，由于二叉树的构成问题属于卡特兰数的一种应用！我们可以直接使用递推式得到最终的结果！

思路一：动态规划

class Solution {
public:
    int numTrees(int n) {
        vector<long> dp(n+1);
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i-j-1];
            }
        }
        return dp[n];
    }
};

思路二：卡特兰数

class Solution {
public:
    int numTrees(int n) {
        long h = 1;
        for(long i = 1; i <= n; ++i){
            h = h * (4*i-2) / (i+1);
        }
        return h;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-binary-search-trees

卡特兰数的其他应用：

• 进出栈问题，假如一个足够大的进栈序列为1,2,3…n, 有多少种不同的出栈序列？
• 二叉树构成问题，假如有1,2,3…n个节点，可以构成多少种不同的二叉树结构？
• 圆内连弦，假设圆周上有2n个点，以这些点为端点连接互不相交的n条弦，可以有多少种连接方法？ （我记得今年头条秋招题目就是这个问题的变形，如果知道卡特兰数很easy的）
• 凸多边形的剖分，求凸n+2边形用其n-1条对角线分割为互不重合的三角形的分发总数？
• 由n对括号形成的合法括号表达式的个数？

推荐阅读博客： http://lanqi.org/interests/10939/