爬楼梯

GitHub跳转原题关系图返回列表

Fibonacci 型递推：dp[i] = dp[i-1] + dp[i-2]，初值 dp[1]=1, dp[2]=2。

OJ: leetcodecn

题目 ID: climbing-stairs

难度:入门

标签:动态规划递推

日期: 2026-07-29 12:29

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

爬 n 阶楼梯，每次可走 1 或 2 步，求方法数。

思路

到达第 i 阶的方法数 = 从第 i-1 阶走 1 步 + 从第 i-2 阶走 2 步，即 dp[i] = dp[i-1] + dp[i-2]。初值 dp[1] = 1，dp[2] = 2。

这是 Fibonacci 数列的平移形式。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    cout << Solution().climbStairs(n) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
class Solution:
    def climbStairs(self, n: int) -> int:
        a = b = 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b


def main():
    print(Solution().climbStairs(int(input())))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(1)O(1)，只需前两个值。

总结

爬楼梯是动态规划入门题：状态定义、转移方程、初值三者缺一不可。dp[i] = dp[i-1] + dp[i-2] 是 Fibonacci 型递推，空间可优化到 O(1)O(1)。