难度: Easy
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
1 <= n <= 45
Submission
运行时间: 44 ms
内存: 14.8 MB
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 2
for i in range(n-2):
a, b = b, a + b
return b
Explain
这个题解使用动态规划的思路。定义状态 dp[i] 表示爬到第 i 阶楼梯的不同方法数量。可以得到状态转移方程：dp[i] = dp[i-1] + dp[i-2]，因为爬到第 i 阶可以从第 i-1 阶爬 1 步，或者从第 i-2 阶爬 2 步。题解中使用两个变量 a 和 b 来代替数组，以节省空间，不断更新 a 和 b 的值，最终得到爬到第 n 阶的方法数量。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 2 # a 表示爬到第 i-2 阶的方法数，b 表示爬到第 i-1 阶的方法数
for i in range(n-2): # 从第 3 阶开始，循环计算爬到第 i 阶的方法数
a, b = b, a + b # 更新 a 和 b 的值，b 变为爬到第 i 阶的方法数
return b # 最终 b 的值即为爬到第 n 阶的方法数
Explore
选择状态转移方程 dp[i] = dp[i-1] + dp[i-2] 是因为要爬到第 i 阶楼梯，有两种方法：从第 i-1 阶楼梯爬一步到达或从第 i-2 阶楼梯爬两步到达。因此，到达第 i 阶的方法数是到达第 i-1 阶的方法数和到达第 i-2 阶的方法数之和。这种关系反映了问题的子结构和重叠子问题，是动态规划解决这类问题的典型表达。
变量 a 和 b 的初始值分别设定为 1 和 2 是因为这是问题的基本情况。当 n=1 时，只有一种方法爬到第一阶（直接1步），因此 dp[1]=1（即变量 a）。当 n=2 时，有两种方法到达第二阶：直接从地面爬两步或先爬一步到第一阶后再爬一步，因此 dp[2]=2（即变量 b）。这两个初始值是后续计算的基础，允许通过迭代递推计算更高阶的答案。
Python中的语句 'a, b = b, a + b' 使用了元组解包的特性，这意味着在赋值操作之前，右侧表达式会先被计算并创建为一个元组 (b, a + b)，然后这个元组被解包并分别赋值给 a 和 b。这个操作是原子的，保证了在赋值过程中变量的值不会相互干扰或丢失，从而正确地更新了两个变量的值。
若要修改程序以打印出所有具体路径，需要使用一个不同的方法来存储路径而不仅仅是数量。可以创建一个列表 dp，其中 dp[i] 存储到达第 i 阶的所有路径的列表。初始时，dp[1] = [['1']]，dp[2] = [['1', '1'], ['2']]。对于每一阶 i > 2，更新 dp[i] 为 dp[i-1] 中每条路径后加 '1' 和 dp[i-2] 中每条路径后加 '2'。最后打印 dp[n] 就可以显示到达第 n 阶的所有路径。这需要更多的空间来存储路径信息，并增加了处理每个阶梯的复杂度。