爬楼梯问题：动态规划与斐波那契的巧妙结合

问题描述

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

示例：

n = 2 → 输出 2（1阶+1阶 或 2阶）
n = 3 → 输出 3（1阶+1阶+1阶、1阶+2阶、2阶+1阶）

约束：1 ≤ n ≤ 45

解题思路

爬楼梯问题本质是斐波那契数列的变种。关键洞察：

到达第 n 阶的最后一步有两种选择：
- 从第 n-1 阶爬 1 阶
- 从第 n-2 阶爬 2 阶
因此，状态转移方程为：
dp[n] = dp[n-1] + dp[n-2]

边界条件

dp[0] = 1（没有台阶时视为一种方法）
dp[1] = 1（爬 1 阶只有一种方法）

解法分析

1. 记忆化搜索（自顶向下）

通过递归+缓存避免重复计算，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ （递归栈深度+缓存数组）。

class Solution {int[] arr = new int[46]; // 缓存数组（n最大为45）public int climbStairs(int n) {return f(n);}private int f(int n) {if (arr[n] != 0) return arr[n]; // 命中缓存if (n == 0 || n == 1) return 1; // 边界条件arr[n] = f(n-1) + f(n-2); // 递归计算并缓存return arr[n];}
}

优势：

直接模拟问题描述，逻辑清晰
避免重复计算，效率较纯递归大幅提升

局限：

递归调用栈可能溢出（尽管本题 n≤45 安全）

2. 动态规划（自底向上）

迭代计算，消除递归开销。时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。

class Solution {public int climbStairs(int n) {if (n <= 1) return 1;int[] dp = new int[n+1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

3. 空间优化动态规划（最优解）

仅需保存前两个状态，空间复杂度优化至 $O (1)$ 。

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

优势：

空间效率最高（常数空间）
运行速度最快（无递归和数组操作开销）

数学视角：斐波那契数列

爬楼梯问题等价于斐波那契数列：

台阶数 `n`	0	1	2	3	4	5
方法数	1	1	2	3	5	8

可直接套用斐波那契通项公式（但浮点运算可能有精度问题）：

public int climbStairs(int n) {double sqrt5 = Math.sqrt(5);return (int) ((Math.pow((1+sqrt5)/2, n+1) - Math.pow((1-sqrt5)/2, n+1)) / sqrt5);
}

注意：通项公式在 n>45 时可能因浮点精度失效，迭代解法更可靠。

总结与对比

方法	时间复杂度	空间复杂度	适用场景
记忆化搜索	$O (n)$	$O (n)$	递归思路清晰
动态规划	$O (n)$	$O (n)$	无栈溢出风险
优化动态规划	$O (n)$	$O (1)$	最优解，推荐使用
通项公式	$O (1)$	$O (1)$	理论价值高，精度受限