java编程求卡特兰数_从一道动态规划题带你领略『卡特兰数』是如何秒杀算法题的...

一、 leetcode 96 号题

题意&＃xff1a;给定一个整数 n&＃xff0c;求以 1 … n 为节点组成的二叉搜索树有多少种&＃xff1f;

n &＃61; 3 时&＃xff1a;

二、动态规划

思路&＃xff1a;从 1 开始到 n &＃xff0c;每次以这个数为根&＃xff0c;左子树存放比它小的数&＃xff0c;右子树存放比它大的数。每个根不重复&＃xff0c;因此每个树也必定不重复。

左子树和右子树&＃xff0c;又可以按照这个规则去生成新的树。

例如&＃xff1a;n &＃61; 3的时候

1为根&＃xff1a;比 1 小的数只有 0&＃xff0c;不用管。比 1 大的数有 2 和 3。

拿 2 和 3 来生成一棵树和拿 1 和 2 来生成一棵树的种数是不是相同的&＃xff1f;那么 1 和 2 能生成多少种树呢&＃xff1f;

2为根&＃xff1a;比 2 小的是 1&＃xff0c;比 2 大的是 3。这里只有 1 种。

3为根&＃xff1a;比 3 小的是 1 和 2&＃xff0c;1 和 2 能生成多少种树呢&＃xff1f;

我们先暂停思维&＃xff0c;来到一个新的问题。n &＃61; 2 的时候&＃xff0c;结果应该是多少&＃xff1f;

n &＃61; 2 的时候&＃xff0c;按照我们之前的方法。

1 为根&＃xff1a;比 1 大的数只有 2&＃xff0c; 这里有 1 种。

2 为根&＃xff1a;比 2 小的数只有 1&＃xff0c; 这里有 1 种。

那答案就应该是 2 种。

解决了 n &＃61; 2 的问题&＃xff0c;那 n &＃61; 3 的问题就也解决了。ans &＃61; 2 &＃43; 1 &＃43; 2 &＃61; 5。

我们来看一般情况。输入一个 n 。

定义一个 F(i) 表示以 i 为根&＃xff0c;生成的树的种数。

定义一个 G(n) 表示输入 n 的时候&＃xff0c;输出的结果。此处一定要注意 F 与 G 的区别。

以 i 为根的时候&＃xff0c;能生成多少种树&＃xff1f;

比 i 小的有 i - 1 个&＃xff0c;比 i 大的有 n - i 个。因此左子树有 i - 1 个&＃xff0c; 右子树有 n - i 个数。那么&＃xff0c;F(i) &＃61; G(i - 1) * G(n - i)。

而我们求的 G(n) &＃61; F(1) &＃43; F(2) &＃43; …… &＃43; F(n)。

把两个公式综合 &＃xff1a;

d[0] &＃61; 1; // 0 的时候特殊处理

for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)

for (int j &＃61; 1; j <&＃61; i; j&＃43;&＃43;)

d[i] &＃43;&＃61; d[j-1] * d[i-j];

以上是利用动态规划求解的思路。

时间复杂度&＃xff1a;O(n^2)

空间复杂度&＃xff1a;O(n)

三、 Catalan公式

这个题目还有一种很强的解法&＃xff0c;卡特兰公式。卡特兰公式和排列组合有很大关系&＃xff0c;不属于偏难怪解法&＃xff0c;有很多算法和数据结构的问题本质上就是卡特兰公式的应用。比如二叉树的形态数&＃xff0c;出栈序列数&＃xff0c;括号匹配问题等。公式不要紧&＃xff0c;没必要去硬背。主要是理解卡特兰问题应用的特征&＃xff0c;把问题抽象到已有模型中来。

Catalan 递推项满足&＃xff1a;

C(n) &＃61; C(0) C(n-1) &＃43; C(1) C(n-2) &＃43; … &＃43; C(n-2) C(1) &＃43; C(n-1) C(0)

Catalan 通项公式&＃xff1a;

&＃61;

Catalan 递推公式1&＃xff1a;

&＃61;

Catalan 性质&＃xff1a;

&＃61;

-

这个题目里面&＃xff0c;由我们上面的 G(n) 很容易可以看出是一个卡特兰的应用。

我们用它的递推公式来求解。

求

的值&＃xff0c;

&＃61;

。公式顺推&＃xff0c;代码中 n 次循环结束后的 ans 值就是

对应的值。类比斐波那契最简解法。

long ans &＃61; 1;

for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)

ans &＃61; ans * 2 * (2 * i &＃43; 1) / (i &＃43; 2);

return (int) ans;

时间复杂度&＃xff1a;O(n)

空间复杂度&＃xff1a;O(1)

四、Catalan应用

例题1&＃xff1a;括号序列

给 n 对括号&＃xff0c;可以合成的合法序列有多少种&＃xff1f;

首先计算一共的序列种数。n 对括号&＃xff0c; 一共有 2n 个位置。我们选出其中 n 个位置放放置左括号&＃xff0c;剩下的位置肯定就是右括号了。因此一共的种数为&＃xff1a;

。

接下来找出非法的括号序列数。每个非法的序列&＃xff0c;在它的奇数位置&＃xff0c;一定存在右括号数量大于左括号的数量。

在上图中&＃xff1a;第 2m &＃43; 1 的时候&＃xff0c;右括号大于左括号&＃xff0c;因此该序列非法。

在 2m &＃43; 1 前&＃xff1a;

右括号数量为&＃xff1a;m &＃43; 1

左括号数量为&＃xff1a;m

在 2m &＃43; 1后&＃xff1a;

总的数量&＃xff1a;n - 2m - 1

左括号有&＃xff1a;n - 2m - 1 - (m &＃43; 1) &＃61; n - m

右括号有&＃xff1a;n - 2m - 1 - m &＃61; n - m - 1

这个时候我们将右边的左括号和右括号位置置换(总的组合数量不会受到影响)。那么在整个序列 2n 个位置中&＃xff1a;

右括号的数量为&＃xff1a;m &＃43; 1 &＃43; n - m &＃61; n &＃43; 1

左括号的数量为&＃xff1a;m &＃43; n - m - 1 &＃61; n - 1

在长度为 2n 里面有 n &＃43; 1 个右括号&＃xff0c;数量为&＃xff1a;

。你也可以理解从左括号的角度去看&＃xff1a;

。

在上面两个步骤以后&＃xff0c;我们得到的合法序列数&＃xff1a;

-

。这就是 Catalan 公式的性质公式。知道是 Catalan&＃xff0c;我们就可以用刚刚的方法求解问题的答案。

例题2 &＃xff1a;一个栈(无穷大)的进栈序列为1&＃xff0c;2&＃xff0c;3&＃xff0c;…&＃xff0c;n&＃xff0c;有多少个不同的出栈序列?

例题3 &＃xff1a;给出一个n&＃xff0c;要求一个长度为2n的01序列&＃xff0c;使得序列的任意前缀中1的个数不少于0的个数&＃xff0c; 有多少个不同的01序列?

例题4 &＃xff1a;2n个人要买票价为五元的电影票&＃xff0c;每人只买一张&＃xff0c;但是售票员没有钱找零。其中&＃xff0c;n个人持有五元&＃xff0c;另外n个人持有十元&＃xff0c;问在不发生找零困难的情况下&＃xff0c;有多少种排队方法&＃xff1f;(阿里有个笔试题根据这个变化的)

其他动态规划算法题推荐&＃xff1a;

1、告别动态规划&＃xff0c;连刷40道动规算法题&＃xff0c;我总结了动规的套路

2、动态规划该如何优化&＃xff1f;我总结了这些套路&＃xff0c;以后优化就是分分钟

3、算法专题(动规)&＃xff1a;不同的定义产生不同的解法

4、详解三道一维的动态规划算法题

5、经典动态规划&＃xff1a;高楼扔鸡蛋

6、详解 leetcode 221 题&＃xff1a;最大正方形

7、动态规划之正则表达式

推荐阅读

写了很久&＃xff0c;这是一份适合普通大众/科班/非科班的『学习路线』

有必要说一说即将到来的春招(经历&＃43;重要性&＃43;如何准备)

普普通通&＃xff0c;我的三年大学

历经两个月&＃xff0c;我的秋招之路结束了&＃xff01;