爬楼梯问题
问题描述
假设你正在爬楼梯，需要爬 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阶和第n-2阶方法数之和。 - 状态转移方程：
dp[n] = dp[n-1] + dp[n-2] - 初始条件：
dp[1] = 1（爬 1 阶）dp[2] = 2（爬 2 阶或两次 1 阶）
使用迭代代替递归以避免重复计算，优化空间复杂度至 (O(1))。
算法实现
java
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n; // 直接返回 n=1 或 n=2 的结果
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int next = a + b; // 计算当前阶数的方法数
a = b; // 更新前两阶的状态
b = next; // 更新前一阶的状态
}
return b;
}
}时间复杂度： (O(n))，遍历一次从 3 到 n。
空间复杂度： (O(1))，仅使用常数变量。
示例计算
以 n = 5 为例：
- 初始：
a = 1（dp[1]），b = 2（dp[2]） - i=3：
next = 1 + 2 = 3→a = 2,b = 3 - i=4：
next = 2 + 3 = 5→a = 3,b = 5 - i=5：
next = 3 + 5 = 8→a = 5,b = 8
输出：8
总结
通过动态规划的迭代方法，高效计算爬楼梯的不同方法数。代码简洁且性能优化，适用于较大 n 值。### 动态规划超大白话解释
想象你要去朋友家玩，但路上有好多条岔路。你想知道从你家到朋友家总共有多少种走法。这就是动态规划要解决的问题！
大白话解释动态规划
举个具体例子 🌰：
假设你家在A点，朋友家在D点，中间有B和C两个点：
A -- B -- C -- D每次只能走一步（比如A到B，或者B到C）
问题：从A到D有多少种走法？
分解小问题：
- 先看A到B：只有1种走法（直接走）
- A到C：2种走法（A→B→C 或 直接A→C？等等...这里需要重新思考）
重新思考正确分解：
- 到B点的走法：1种（A→B）
- 到C点的走法：2种（A→B→C 或 A→C）
- 到D点的走法：需要从C点走过来（因为只能走一步）
关键发现：
- 想到D点，必须先到C点
- 所以到D的方法数 = 到C的方法数
- 到C的方法数 = 到B的方法数 + 直接到C的方法
建立"记忆本"：
位置 从A出发的方法数 怎么算出来的 B 1 直接走 C 2 (到B的方法)+1 D 2 等于到C的方法 这就是动态规划：
- 把大问题（去D点）拆成小问题（先去B、C点）
- 用表格记录每个点的答案
- 后面的答案用前面的答案算出来
- 避免重复计算（比如算D时直接查C的记录）
爬楼梯就是这样的问题：
- 到第3级台阶 = (到第2级的方法) + (到第1级的方法)
- 因为：从第2级走1步，或者从第1级走2步
动态规划三步骤：
- 拆零件：把大问题拆成小问题（比如拆解成到每一级台阶的方法）
- 记答案：用表格记录每个小问题的答案
- 拼起来：用前面小问题的答案组合出大问题的答案
为什么叫"动态"规划？
因为答案像搭积木一样：
- 先算台阶1：1种方法
- 再算台阶2：2种方法
- 然后台阶3 = 台阶1 + 台阶2 = 3
- 台阶4 = 台阶2 + 台阶3 = 5
- 像滚雪球一样越滚越大！
生活比喻：
就像吃奥利奥饼干：
- 先拆开包装（拆解问题）
- 记住第一片饼干的味道（记录小答案）
- 用第一片的经验吃第二片（组合答案）
- 最后知道整包饼干的味道（解决大问题）
这样每次遇到新问题，都不用从头开始想，直接查之前的"记忆小本本"就行啦！🍪