题目描述 顽皮的小明发现，下楼梯时每步可以走 1 个台阶、 2 个台阶或 3 个台阶。现在一共有 N N 个台阶，你能帮小明算算有多少种方案吗？ 输入格式 输入一行，包含一个整数 N N。 输出格式 输出一行一个整数表示答案。

这是一个典型的动态规划问题。设 `dp[i]` 表示走到第 `i` 个台阶的方案数。 对于第 `i` 个台阶，小明可以从第 `i - 1` 个台阶走 1 步到达，也可以从第 `i - 2` 个台阶走 2 步到达，还可以从第 `i - 3` 个台阶走 3 步到达。所以状态转移方程为：`dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]`。 以下是使用 Python 实现的代码： ```python # 读取输入的台阶数 n = int(input()) # 初始化 dp 数组 dp = [0] * (n + 1) # 初始化边界条件 if n >= 0: dp[0] = 1 # 站在第 0 个台阶有一种方案，即不移动 if n >= 1: dp[1] = 1 # 走到第 1 个台阶只有一种方案，走 1 步 if n >= 2: dp[2] = 2 # 走到第 2 个台阶有两种方案，走两个 1 步或走一个 2 步 # 动态规划计算 dp 数组 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] # 输出结果 print(dp[n]) ``` 复杂度分析 - 时间复杂度：代码中有一个循环从 3 到 `n`，因此时间复杂度为 $O(n)$。 - 空间复杂度：使用了一个长度为 `n + 1` 的数组 `dp` 来保存中间结果，因此空间复杂度为 $O(n)$。 [2026-01-10 20:37:23 | AI问答 | 429点数解答]