一、文章标题 LeetCode 070. 爬楼梯 - 动态规划与斐波那契优化详解

二、文章内容

1. 题目概述

• 题目描述：给定一个正整数 n，代表楼梯的阶数。每次你可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶（到达第 n 阶）。
• 原题链接：https://leetcode.cn/problems/climbing-stairs/
• 难度等级：Easy
• 相关标签：动态规划、数学、斐波那契、滚动数组

2. 文章目录

目录

1. 题目概述
2. 解题思路
3. 算法详解
   • 3.1 解法一：动态规划（数组版）
   • 3.2 解法二：滚动变量（斐波那契迭代）
4. 解法对比
5. 最优解推荐

3. 解题思路

• 问题分析：
  • 输入：一个整数 n（n ≥ 1），表示台阶数。
  • 规则：每次只能爬 1 阶或 2 阶。
  • 目标：返回到达第 n 阶的不同方式数量。
  • 输出：一个整数 ways(n)。
• 核心难点：
  • 正确建立递推关系：f(n) = f(n-1) + f(n-2)，因为最后一步要么 1 阶（来自 n-1），要么 2 阶（来自 n-2）。
  • 明确边界：f(1) = 1，f(2) = 2。
  • 在保证正确性的同时优化空间复杂度。
• 解题方向：
  1. 动态规划数组版：自底向上填表，清晰直观；
  2. 滚动变量（斐波那契迭代）：仅用常数个变量维护 f(n-1)、f(n-2)，将空间降至 O(1)；
  3. 拓展（不展开实现）：矩阵快速幂或快速倍增可将时间降为 O(log n)。

4. 算法详解

解法一：动态规划（数组版）

算法原理

• 将问题映射为斐波那契数列：f(n) = f(n-1) + f(n-2)，且 f(1)=1, f(2)=2。
• 自底向上利用数组 dp 记录每个台阶的方案数，避免重复计算。
• 适用场景：入门友好、便于调试和展示完整状态演化。

具体实现

• 步骤1：判空和边界：n ≤ 0 返回 0，n==1 返回 1，n==2 返回 2。
• 步骤2：创建长度为 n+1 的数组 dp，初始化 dp[1]=1，dp[2]=2。
• 步骤3：从 3 循环到 n，应用转移 dp[i]=dp[i-1]+dp[i-2]。
• 步骤4：返回 dp[n]。

复杂度分析

• 时间复杂度：O(n)，线性遍历计算每个状态一次。
• 空间复杂度：O(n)，使用长度为 n+1 的数组存储中间结果。

Java代码实现

class Solution {
    /**
     * 解法一：动态规划（数组版）
     * 使用 dp[i] 表示到达第 i 阶的不同方法数。
     * 注意：为简化边界处理，约定 n<=0 时返回 0 作为默认值，避免抛出异常。
     */
    public int climbStairsDP(int n) {
        // 边界处理：n<=0 时返回 0；n==1、n==2 直接返回
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1; // 只有 1 种方法：一步
        }
        if (n == 2) {
            return 2; // 两种方法：1+1 或 2
        }

        // dp[i] 表示到达第 i 阶的不同方法数
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        // 自底向上填表：每次只能从 i-1 或 i-2 到达 i
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回结果
        return dp[n];
    }
}

解法二：滚动变量（斐波那契迭代）

算法原理

• 利用递推只依赖前两项的性质，使用两个变量滚动维护 f(n-1)、f(n-2)，将空间降到 O(1)。
• 适用场景：数据规模较大、对空间敏感或追求最简写法的场景。

具体实现

• 步骤1：处理 n≤0、n==1、n==2 的边界。
• 步骤2：使用 prev2 表示 f(i-2)，prev1 表示 f(i-1)，初始为 1、2。
• 步骤3：循环 i=3..n，计算 cur=prev1+prev2，然后滚动：prev2=prev1，prev1=cur。
• 步骤4：返回 prev1。

复杂度分析

• 时间复杂度：O(n)，单循环计算到第 n 项。
• 空间复杂度：O(1)，仅用常数个变量。

Java代码实现

class Solution {
    /**
     * 解法二：滚动变量（推荐）
     * 将空间优化到 O(1)，对应斐波那契迭代。
     * 同样对 n<=0 返回 0，避免异常。
     */
    public int climbStairs(int n) {
        // 边界处理
        if (n <= 0) {
            return 0; // 默认返回 0
        }
        if (n == 1) {
            return 1; // 只有一种方法
        }
        if (n == 2) {
            return 2; // 两种方法
        }

        // prev2 = f(i-2), prev1 = f(i-1)
        int prev2 = 1; // f(1)
        int prev1 = 2; // f(2)

        // 从第 3 阶开始迭代到第 n 阶
        for (int i = 3; i <= n; i++) {
            int cur = prev1 + prev2; // f(i) = f(i-1) + f(i-2)
            // 滚动更新：前移两个指针
            prev2 = prev1;
            prev1 = cur;
        }

        return prev1; // f(n)
    }
}

5. 解法对比与总结

| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | 适用场景 | |------|------------|------------|------|------|----------| | 动态规划（数组版） | O(n) | O(n) | 思路直观、便于调试与讲解 | 额外空间为 O(n) | 学习入门、需要展示完整状态 | | 滚动变量（斐波那契迭代） | O(n) | O(1) | 代码简洁、空间最优 | 可读性略低于数组版（对新手） | 面试与工程实践优先 |

最优解推荐：综合时间、空间与可读性，推荐“滚动变量（斐波那契迭代）”解法，O(n) 时间 + O(1) 空间，满足绝大多数场景。

三、文章标签 算法,动态规划,LeetCode,简单,斐波那契,滚动数组

四、文章简述 经典简单题“爬楼梯”，用动态规划建模为斐波那契递推，先给出数组版 O(n) 空间，再用滚动变量将空间降至 O(1)。详解边界与状态转移，含完整 Java 注释代码与复杂度分析，适合刷题入门与面试速记。