通过率 64% · 提交 140 · 通过 89
这道 OJ 的配套动画
动态规划状态与转移 · 对应本题的思路、过程和代码
你一次可以爬 1 阶或 2 阶。给定台阶数 n，请输出爬到第 n 阶共有多少种不同方法。
这题属于 Hot100 ACM 开放训练中的「动态规划入门」方向。建议先看动画确认核心思路，再回到右侧编辑器按标准输入输出写完整代码。
输入一个整数 n。
输出一个整数，表示方法数。
示例 1
输入示例
3
输出示例
3
可以是 1+1+1、1+2、2+1。
时间限制 2000 ms · 内存限制 256 MB
训练营动画视频讲解
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
设 dp[i] 为到达第 i 阶的方法数。最后一步只有两种可能：从第 i-1 阶迈 1 阶，或从第 i-2 阶迈 2 阶，因此 dp[i]=dp[i-1]+dp[i-2]。初始化 dp[1]=1、dp[2]=2，只保留相邻两项即可。
按最后一步分类，两类方案互不重叠且覆盖所有到达第 i 阶的方法。删除最后一步后，分别与到达第 i-1 阶和第 i-2 阶的方法一一对应，所以递推式成立。
执行 n-2 次大整数加法，循环次数为 O(n)，滚动状态只保存两个大整数。若计入大整数位数，单次加法成本随答案位数增长。
n=1 和 n=2 直接输出初值。题面未给出可证明的 n 上界，因此 C++ 使用十进制字符串实现大整数加法，Java 使用 BigInteger，避免固定宽度整数溢出。
n = int(input())
if n <= 2:
print(n)
else:
previous_two, previous_one = 1, 2
for _ in range(3, n + 1):
previous_two, previous_one = previous_one, previous_two + previous_one
print(previous_one)