---

扩展楼梯

题目描述

小明正在爬楼梯。

楼梯一共有 $n$ 阶，小明每次可以向上走 $1$ 阶、$2$ 阶或 $3$ 阶。

请你计算：小明从第 $0$ 阶出发，恰好走到第 $n$ 阶，一共有多少种不同的走法。

两种走法不同，当且仅当每一步走的阶数序列不同。

例如，当 $n=3$ 时，共有 $4$ 种走法：

1 + 1 + 1
1 + 2
2 + 1
3

因此答案为 4。

---

输入格式

输入一个正整数 $n$，表示楼梯的阶数。

---

输出格式

输出一个整数，表示走到第 $n$ 阶的方案数。

---

样例输入 1

3

样例输出 1

4

---

样例输入 2

5

样例输出 2

13

---

样例解释

当 $n=5$ 时，方案数满足：

dp[1] = 1
dp[2] = 2
dp[3] = 4
dp[4] = dp[3] + dp[2] + dp[1] = 7
dp[5] = dp[4] + dp[3] + dp[2] = 13

所以答案为 13。

---

数据范围

对于 $100$ 的数据，满足：

$$1 \le n \le 30$$

---

题目分析

设 dp[i] 表示走到第 $i$ 阶的方案数。

要走到第 $i$ 阶，最后一步可能是：

• 从第 $i-1$ 阶走 $1$ 阶到达；
• 从第 $i-2$ 阶走 $2$ 阶到达；
• 从第 $i-3$ 阶走 $3$ 阶到达。

因此状态转移方程为：

$$dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$$

初始值为：

$$dp[1] = 1$$ $$dp[2] = 2$$ $$dp[3] = 4$$

---