OIer博客

小虎刚刚上了幼儿园，老师让他做一个家庭作业：首先画 $3$ 行格子，第一行有三个格子，第二行有 $2$ 个格子，第三行有 $1$ 个格子。每行的格子从左到右可以放棋子，但要求除第一行外，每行放的棋子数不能超过上一行的棋子。第一行的棋子数不能为 $0$，但剩下行可以为空。玩了一会儿，小虎对哥哥大虎说：”这个作业有很多种摆放法，我想找到，但我不知道有多少种方案，你能帮助我吗？”

大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：$13$。

第二天他把问题拿到学校，并说如果第一行有 $N$ 个格子，第二行有 $N-1$ 个格子，……，第 $N$ 行有 $1$ 个格子，怎么办？现在请你一块来帮助他解决这个难题。

仅一行，一个正整数 $N$。

一行，方案总数。

2

4

3

13

样例 1 说明：$N=2$ 时，有如下 $4$ 种摆放棋子法（ `*` 表示棋子，`_` 表示空格）：
| 方案数| 1 | 2 | 3 | 4 |
| :———– | :———– | :———– | :———– | :———– |
| **第一行** | `*_` | `**` | `*_` | `**` |
| **第二行** | `_` | `_` | `*` | `*` |对于 $30\%$ 数据：$1\le N\le 12$。

对于 $50\%$ 数据：$1\le N\le 30$。

对于 $100\%$ 数据：$1\le N\le 100$。