70. 爬楼梯

问题描述

假设你正在爬楼梯。需要爬完 n 阶台阶才能到达楼顶。每次你可以爬 1 或 2 个台阶。计算有多少种不同的方法可以爬到楼顶。

示例：

输入：n = 2
输出：2
解释：有两种方法：
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法：
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

算法思路

动态规划（斐波那契数列变体）：

1. 状态定义：dp[i] 表示爬到第 i 阶台阶的方法数。
2. 状态转移：
   • 到达第 i 阶的方法 = 从第 i-1 阶爬 1 阶 + 从第 i-2 阶爬 2 阶
     dp[i] = dp[i-1] + dp[i-2]
3. 初始化：
   • dp[0] = 1（起点，0阶有1种方法：不动）
   • dp[1] = 1（爬1阶：1种方法）
4. 遍历顺序：从 2 到 n 顺序计算。

空间优化：

• 由于 dp[i] 只依赖前两个状态，用两个变量滚动存储即可。

代码实现

方法一：动态规划（DP 数组）

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1; // 边界处理：0阶或1阶直接返回1
        
        int[] dp = new int[n + 1]; // dp[i] 表示爬到第 i 阶的方法数
        dp[0] = 1; // 初始状态：0阶有1种方法（不动）
        dp[1] = 1; // 初始状态：1阶有1种方法（爬1阶）
        
        // 从第2阶开始递推
        for (int i = 2; i <= n; i++) {
            // 状态转移：从 i-1 阶爬1阶 或 从 i-2 阶爬2阶
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n]; // 返回爬到第 n 阶的方法数
    }
}

方法二：动态规划（空间优化）

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1; // 边界处理
        
        int prev1 = 1; // 相当于 dp[0]
        int prev2 = 1; // 相当于 dp[1]
        
        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2; // 计算 dp[i]
            // 滚动更新状态
            prev1 = prev2;   // prev1 更新为上一轮的 prev2（即 dp[i-1]）
            prev2 = current; // prev2 更新为当前值（即 dp[i]）
        }
        return prev2; // 循环结束时 prev2 存储 dp[n]
    }
}

算法分析

• 时间复杂度：O(n)
  只需遍历一次。
• 空间复杂度：
  • 方法一：O(n)（DP 数组）
  • 方法二：O(1)（两个变量）

算法过程

n=4

1. 初始化：
   • prev1 = 1（dp[0]）
   • prev2 = 1（dp[1]）
2. 迭代过程：
   • i=2：current = 1+1=2 → prev1=1, prev2=2
   • i=3：current = 1+2=3 → prev1=2, prev2=3
   • i=4：current = 2+3=5 → prev1=3, prev2=5
3. 结果：prev2=5

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1: n=2（边界）
    System.out.println("n=2: " + solution.climbStairs(2)); // 2
    
    // 测试用例2: n=3（标准）
    System.out.println("n=3: " + solution.climbStairs(3)); // 3
    
    // 测试用例3: n=1（边界）
    System.out.println("n=1: " + solution.climbStairs(1)); // 1
    
    // 测试用例4: n=5（验证递推）
    System.out.println("n=5: " + solution.climbStairs(5)); // 8
    
    // 测试用例5: n=0（特殊边界）
    System.out.println("n=0: " + solution.climbStairs(0)); // 1
}

关键点

1. 状态转移本质：斐波那契数列（dp[i]=dp[i-1]+dp[i-2]）。
2. 初始化意义：
   • dp[0]=1：起点有1种方法（不动）。
   • dp[1]=1：爬1阶只有1种方式。
3. 空间优化核心：
   • 用 prev1 和 prev2 滚动存储前两个状态。
   • 每轮更新后，prev2 始终指向当前最高阶的方法数。

常见问题

1. 为什么 dp[0]=1？
   数学定义：到达起点（0阶）本身是一种方案（无需操作），保证状态转移一致性（dp[2]=dp[1]+dp[0]=1+1=2）。
2. 能否用递归实现？
   可以，但时间复杂度 O(2ⁿ) 会超时，需用备忘录优化。
3. 如何验证结果？
   小规模验证：
   • n=1 → 1种
   • n=2 → 2种
   • n=3 → 3种
   • n=4 → 5种（斐波那契数列）