LeetCode 70. 爬楼梯

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：完全背包
相似题目

题目描述

✅ 70. 爬楼梯

思路分析

解法一：动态规划（推荐）

核心思路：

到达第 n 阶只有两种方式：从第 n-1 阶迈 1 步，或从第 n-2 阶迈 2 步。

状态转移方程：dp[n] = dp[n-1] + dp[n-2]，初始值 dp[1] = 1, dp[2] = 2。

这正是斐波那契数列的递推形式，只依赖前两项，可用滚动变量将空间从 O(n) 优化至 O(1)。

复杂度分析：

时间复杂度：O(n)，其中 n 为台阶数

空间复杂度：O(1)，滚动变量优化

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        // 滚动变量：a 表示 dp[i-2]，b 表示 dp[i-1]
        int a = 1, b = 1;
        for (int i = 2; i <= n; i++) {
            // 当前台阶方案数 = 前一阶 + 前两阶
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    // a 表示 dp[i-2]，b 表示 dp[i-1]
    a, b := 1, 1
    for i := 2; i <= n; i++ {
        // 当前台阶方案数 = 前一阶 + 前两阶
        a, b = b, a+b
    }
    return b
}

解法二：完全背包

核心思路：

将问题转化为完全背包：背包容量为 n，物品为 [1, 2]（每次可走步数），每种物品可无限使用，求恰好装满背包的方案总数。

初始化 dp[0] = 1（空台阶有 1 种方式），对每个台阶 i 从 1 到 n，遍历所有可走步数 j，累加 dp[i] += dp[i-j]。

完全背包求排列数：外层遍历背包容量，内层遍历物品（顺序有关，不同走法顺序不同算不同方案）。

复杂度分析：

时间复杂度：O(n × k)，其中 n 为台阶数，k 为可走步数种类（本题 k=2，即 O(n)）

空间复杂度：O(n)，dp 数组大小

class Solution {
    public int climbStairs(int n) {
        int[] steps = {1, 2};
        // dp[i] 表示到达第 i 阶的方案数
        int[] dp = new int[n + 1];
        dp[0] = 1;
        // 外层遍历背包容量（台阶数），内层遍历物品（步数），求排列数
        for (int i = 1; i <= n; i++) {
            for (int step : steps) {
                if (i >= step) {
                    dp[i] += dp[i - step];
                }
            }
        }
        return dp[n];
    }
}

func climbStairs(n int) int {
    steps := []int{1, 2}
    // dp[i] 表示到达第 i 阶的方案数
    dp := make([]int, n+1)
    dp[0] = 1
    // 外层遍历背包容量（台阶数），内层遍历物品（步数），求排列数
    for i := 1; i <= n; i++ {
        for _, step := range steps {
            if i >= step {
                dp[i] += dp[i-step]
            }
        }
    }
    return dp[n]
}

相似题目

题目	难度	考察点
746. 使用最小花费爬楼梯	简单	动态规划
509. 斐波那契数	简单	递推、记忆化搜索
198. 打家劫舍	中等	动态规划
91. 解码方法	中等	线性 DP
322. 零钱兑换	中等	完全背包
55. 跳跃游戏	中等	贪心 / DP
377. 组合总和 Ⅳ	中等	完全背包、排列数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/77096845