Climbing Stairs
你站在一段有 n 级台阶的楼梯底部。每次可以走 1 级或 2 级。如果行走顺序不同，就算作不同的走法，所以 1, 2 和 2, 1 是两种走法。你的函数接收 n，并返回到达顶部的不同走法数量。
函数
- ninteger
- 楼梯的台阶数
- 返回值integer
- 到达第 n 级台阶的不同 1 步和 2 步序列的数量
约束条件
1 ≤ n ≤ 45- 答案可以用有符号 32 位整数表示：
n = 45得到1836311903。
示例
- 输入
- n = 3
- 输出
- 3
- 解释
- 可以按
1, 1, 1、1, 2或2, 1这三种方式爬完三级台阶。
- 输入
- n = 5
- 输出
- 8
- 解释
- 每次到达第 5 阶，都要么从第 4 阶迈 1 步（有 5 种走法），要么从第 3 阶迈 2 步（有 3 种走法），所以答案是
5 + 3 = 8。
进阶
如果有些台阶坏了，你可能永远无法踩上去，该如何调整递推关系？坏掉的台阶对应的数量是多少？
提示
逐个打开提示，每个都会多透露一点。
看看任何一种爬到第
n级的方法的最后一步。在这一步之前，你可能站在哪一级？每次爬到第
n级台阶，最后一步要么是从第n-1级迈 1 步，要么是从第n-2级迈 2 步，不可能同时是这两种情况。因此，到达第n级台阶的方式数等于到达第n-1级和第n-2级台阶的方式数之和。从走 1 级台阶（1 种走法）和走 2 级台阶（2 种走法）的情况开始，逐步往上推。你只需要保留前两个计数，每次的新计数都是它们的和。
题解
列出每一种攀爬方式行不通：45 级台阶就有 1836311903 种。攀爬到第 n 级台阶时，最后一步之前一定在第 n-1 级或第 n-2 级，因此 ways(n) = ways(n-1) + ways(n-2)，这就是斐波那契递推关系。从底部开始逐步计算，只需要两个变量。
对最后一步进行简单递归
结果正确，但无法在最大的测试中运行完毕
思路
按最后一步来拆分到达第 n 阶的所有走法。最后走 1 阶的走法都经过第 n-1 阶，最后走 2 阶的走法都经过第 n-2 阶，而且没有走法同时属于这两种情况，所以两种走法数相加。走 1 阶有一种走法，走 2 阶有两种，因此当 n ≤ 2 时返回 n。
递归会忘记已经计算过的结果。climbStairs(5) 会两次请求第 3 阶的结果，三次请求第 2 阶的结果，总共调用 9 次；而 n = 45 时会调用 2269806339 次。
算法
- 如果
n ≤ 2，返回n。 - 通过一次递归调用，统计到达第
n-1级台阶的爬法数量。 - 通过第二次递归调用，统计到达第
n-2级台阶的爬法数量。 - 返回两种爬法数量之和。
def climbStairs(n):
if n <= 2:
return n # 1 step: one way, 2 steps: two ways
return climbStairs(n - 1) + climbStairs(n - 2)使用备忘录进行递归
思路
步骤 k 的计数只取决于 k，因此一旦确定就不会改变。第一次计算时，将结果写入备忘槽，之后每次请求都读取槽中的值，而不再递归。这样，从步骤 3 到步骤 n 的每个计数只计算一次，每次只需进行一次加法：时间复杂度为 O(n)。当 n = 5 时，第二次请求步骤 3 会直接查找。
槽中的 0 表示尚未计算，这样做是安全的，因为每个实际计数都至少为 1。
算法
- 创建一个有
n + 1个槽位、初始值都为 0 的备忘录。 - 在递归辅助函数中，当
k ≤ 2时返回k。 - 如果
k对应的备忘录槽位为 0，就将辅助函数对k-1和k-2的返回结果相加后填入该槽位。 - 返回该备忘录槽位。
- 对
n调用辅助函数。
def climbStairs(n):
memo = [0] * (n + 1) # memo[k] = ways to reach step k, 0 = not known yet
def ways(k):
if k <= 2:
return k
if memo[k] == 0:
memo[k] = ways(k - 1) + ways(k - 2)
return memo[k]
return ways(n)使用两个变量自底向上
思路
改为从小到大计算。计算第 k 步的数量时，只需读取第 k-1 步和第 k-2 步的数量，不再需要更早的数量。因此，可以用两个变量代替备忘录。
对于 n = 5，数对 (prev, curr) 会从 (1, 2) 依次变为 (2, 3)、(3, 5) 和 (5, 8)，而 curr = 8 就是答案。覆盖 prev 之前，先计算 next，否则求和时会用错值。
算法
- 如果
n ≤ 2，返回n。 - 设置
prev = 1和curr = 2。 - 对于从 3 到
n的k，计算next = prev + curr，然后设置prev = curr和curr = next。 - 返回
curr。
def climbStairs(n):
if n <= 2:
return n
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(n - 2):
prev, curr = curr, prev + curr
return curr
易错点和边界情况
- 基础情况错误。爬 2 级台阶有两种方法：
1, 1和2。如果n = 2时返回 1，后面的每个答案都会偏小：n = 3时你会得到 2，而不是 3。 - 统计选择，而不是序列。只统计你走了多少次 2 级台阶，得到的是
n/2 + 1，n = 5时结果为 3，而不是 8。 - 没有边界检查就填充表格。
n = 1时，大小为n + 1 = 2的表格没有位置存放第 2 级台阶的结果。先在n ≤ 2时返回n。 - 多运行了一步。爬 46 级台阶的计数是 2971215073，这会超出 Java、C 或 C# 中 32 位
int的范围，变成负数。
常见问题3
为什么爬楼梯问题是斐波那契问题？
每次爬到第 n 级台阶，最后一步要么是从 n-1 级迈 1 步，要么是从 n-2 级迈 2 步，这符合斐波那契规则。已知 ways(1) = 1 和 ways(2) = 2，方案数依次为 1、2、3、5、8、13：这是向后移一位的斐波那契数列，即 ways(n) = F(n+1)。
爬楼梯问题的时间复杂度是多少？
自底向上的循环会进行 n-2 次加法：时间复杂度为 O(n)，额外空间复杂度为 O(1)。使用记忆化的递归时间复杂度为 O(n)，空间复杂度为 O(n)。普通递归的时间复杂度呈指数级增长，每一步的调用次数约增加到原来的 1.618 倍。
每次可以走 1、2 或 3 级台阶，怎么解决爬楼梯问题？
再次按最后一步拆分爬楼梯的方式：ways(n) = ways(n-1) + ways(n-2) + ways(n-3)。从 ways(0) = 1（空爬法）、ways(1) = 1 和 ways(2) = 2 开始，并保留最近三个计数，而不是两个。时间复杂度仍为 O(n)，空间复杂度为 O(1)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def climbStairs(n):
# 在这里编写代码测试 #1
测试 #2
参数
n = 3
预期输出
3