专栏首页苦逼的码农从一道动态规划题带你领略『卡特兰数』是如何秒杀算法题的

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

来源公众号:苦逼的码农

作者:stul

一、 leetcode 96 号题

题目链接:https://leetcode-cn.com/problems/unique-binary-search-trees/

题意:给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?

n = 3 时:

二、动态规划

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

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

例如:n = 3的时候

1为根:比 1 小的数只有 0,不用管。比 1 大的数有 2 和 3。

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

2为根:比 2 小的是 1,比 2 大的是 3。这里只有 1 种。

3为根:比 3 小的是 1 和 2,1 和 2 能生成多少种树呢?

我们先暂停思维,来到一个新的问题。n = 2 的时候,结果应该是多少?

n = 2 的时候,按照我们之前的方法。

1 为根:比 1 大的数只有 2, 这里有 1 种。 2 为根:比 2 小的数只有 1, 这里有 1 种。

那答案就应该是 2 种。

解决了 n = 2 的问题,那 n = 3 的问题就也解决了。ans = 2 + 1 + 2 = 5。

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

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

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

以 i 为根的时候,能生成多少种树?

比 i 小的有 i - 1 个,比 i 大的有 n - i 个。因此左子树有 i - 1 个, 右子树有 n - i 个数。那么,F(i) = G(i - 1) * G(n - i)。

而我们求的 G(n) = F(1) + F(2) + …… + F(n)。

把两个公式综合 :

d[0] = 1; // 0 的时候特殊处理
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++) 
        d[i] += d[j-1] * d[i-j]; 

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

时间复杂度:O(n^2)

空间复杂度:O(n)

三、 Catalan公式

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

Catalan 递推项满足:

C(n) = C(0) * C(n-1) + C(1) * C(n-2) + … + C(n-2) * C(1) + C(n-1) * C(0)

Catalan 通项公式:

=

Catalan 递推公式1:

=

Catalan 性质:

=

-

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

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

的值,

=

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

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

    long ans = 1;
    for(int i = 1; i <= n; i++)
        ans = ans * 2 * (2 * i + 1) / (i + 2);
    return (int) ans;

时间复杂度:O(n)

空间复杂度:O(1)

四、Catalan应用

例题1:括号序列

给 n 对括号,可以合成的合法序列有多少种?

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

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

在上图中:第 2m + 1 的时候,右括号大于左括号,因此该序列非法。

在 2m + 1 前:

右括号数量为:m + 1

左括号数量为:m

在 2m + 1后:

总的数量:n - 2m - 1

左括号有:n - 2m - 1 - (m + 1) = n - m

右括号有:n - 2m - 1 - m = n - m - 1

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

右括号的数量为:m + 1 + n - m = n + 1

左括号的数量为:m + n - m - 1 = n - 1

在长度为 2n 里面有 n + 1 个右括号,数量为:

。你也可以理解从左括号的角度去看:

在上面两个步骤以后,我们得到的合法序列数:

-

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

例题2 :一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?

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

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

本文分享自微信公众号 - 苦逼的码农(di201805),作者:stul

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划之 KMP 算法详解

    KMP 算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,效率很高,但是确实有点复杂。

    帅地
  • 如何理解二分查找?生活中还能用来设计骗局?

    版权声明:本文为苦逼的码农原创。未经同意禁止任何形式转载,特别是那些复制粘贴到别的平台的,否则,必定追究。欢迎大家多多转发,谢谢。

    帅地
  • 【算法题】韩信点兵:如何优雅移动士兵?

    自从“韩信点兵,多多益善”事件之后,韩信的麻烦事就来了。这不,今天刘邦又找他麻烦了。

    帅地
  • 视频颜色理论

    本文来自“The Broadcast Knowledge”的演讲,主题是“视频颜色理论”,演讲者是Korro电影公司所有者兼创意总监Ollie Kenching...

    用户1324186
  • leetcode-22-括号生成

    给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

    chenjx85
  • keras实现调用自己训练的模型,并去掉全连接层

    以上这篇keras实现调用自己训练的模型,并去掉全连接层就是小编分享给大家的全部内容了,希望能给大家一个参考。

    砸漏
  • ASP.NET中各命名空间及作用

    System                            包含了基础类,用于定义类型/数组/字符串/事件/事件处理程序/异常 处理 /接口/数据类型转...

    DougWang
  • 【Pygame 第6课】 面向对象的游戏设计

    上节课中,我们的飞机已经可以发射子弹了,尽管只有一颗。为什么我只加了一颗?试着多加几颗你就会发现,你得用好几个变量去分别记录它们的xy坐标,在主循环中判断每一颗...

    Crossin先生
  • 树莓派基础实验11:U型光电传感器实验

       U型光电传感器是一种对射式光电传感器,它有一个发射端和接收端组成。它的工作原理是通过对红外发射光的阻断和导通,在红外接收管感应出的电流变化来实现开和关的判...

    张国平
  • 快速学习-Mybatis 的动态 SQL 语句

    Mybatis 的映射文件中,前面我们的 SQL 都是比较简单的,有些时候业务逻辑复杂时,我们的 SQL 是动态变化的,此时在前面的学习中我们的 SQL 就不能...

    cwl_java

扫码关注云+社区

领取腾讯云代金券