Processing math: 100%
编程题
                ### 问题描述

卡特兰遇到了一个非常棘手的问题,他现在有许多对括号,他想知道这些括号有多少种有效的组合方式。

一个有效的括号配对定义为:

  1. 每个开括号 ( 后面都必须在某个位置有一个对应的闭括号 )
  2. 对于任意位置,从字符串的开始到这个位置,开括号的数量都不少于闭括号的数量。换句话说,在任何时刻,不能出现已经关闭的括号数量超过已经打开的括号数量的情况。

利用这些定义,我们可以确保:

  1. 所有开括号都有闭括号与之配对。
  2. 不会出现像 )( 这样的无效组合。
  3. 字符串中的每一个括号都有其有效的作用,没有多余的开或闭括号。

给定一个整数 n,代表 n 对括号。你的任务是确定这 n 对括号能够生成多少种有效的配对方法。一个有效的括号配对是指每一个开括号都与一个闭括号正确配对,并且没有多余的开或闭括号。

例如,对于 n=3,存在的有效配对有 ((()))(()())(())()()(())()()()

输入格式

一个整数 n(1n30),代表括号的对数。

输出格式

一个整数,表示 n 对括号能形成的有效配对方法数。

样例输入

3

样例输出

5

样例说明

如上述问题描述中提到的,对于 n=3,存在的有效配对有 5 种:((()))(()())(())()()(())()()()

测评数据规模

输入中的整数 n 满足 1n30

查看答案
赣ICP备20007335号-2