1 问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

2 示例

示例1：
输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。
1: 1 阶 + 1 阶
2: 2 阶

示例 2：
输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。
1: 1 阶 + 1 阶 + 1 阶
2: 1 阶 + 2 阶
3: 2 阶 + 1 阶

3 解法

3.1 暴力破解

采用递归的方法：将会把所有可能爬的阶数进行组合，也就是 $1$ 和 $2$ 。而在每一步中我们都会继续调用 $climbStairs$ 这个函数模拟爬 $1$ 阶和 $2$ 阶的情形，并返回两个函数的返回值之和。

$climbStairs(i, n)=(i+1, n)+climbStairs(i+2, n)$

其中 $i$ 定义了当前阶数，而 $n$ 定义了目标阶数。

在 $n=5$ 时，递归树是这样的：
Python3实现：

n = 3
def solution(n):
	return climbStairs(0, n)

def climbStairs(i, n):
	if i > n:
		return 0
	elif i == n:
		return 1
	else:
		return climbStairs(i+1, n) + climbStairs(i+2, n)

if __name__ == "__main__":
	print (solution(n))

3.2 记忆化递归

在上一种方法中，我们计算每一步的结果时出现了冗余，观察上图的递归树可以看出， $(4,5)$ 在树中出现了许多次，而用 $memo[4]$ 可以直接记忆 $i=4$ 时的方法数。因此我们可以把每一步的结果存储在 $memo$ 数组之中，每当函数再次被调用，我们就直接从 $memo$ 数组返回结果。
在 $memo$ 数组的帮助下，我们得到了一个修复的递归树，其大小减少到 $n$ 。
Python3实现：

n = 3
def solution(n):
	memo = [0]*n
	return climbStairs(0, n, memo)

def climbStairs(i, n, memo):
	if i > n:
		return 0
	elif i == n:
		return 1
	elif memo[i] > 0:
		return memo[i]
	else:
		memo[i] = climbStairs(i+1, n, memo) + climbStairs(i+2, n, memo)
		return memo[i]

if __name__ == "__main__":
	print (solution(n))

3.3 动态规划法

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。
第 $i$ 阶可以由以下两种方法得到：
- 在第 $(i-1)$ 阶后向上爬 $1$ 阶。
- 在第 $(i-2)$ 阶后向上爬 $2$ 阶。
所以到达第 $i$ 阶的方法总数就是到第 $(i−1)$ 阶和第 $(i−2)$ 阶的方法数之和。
令 $dp[i]$ 表示能到达第 $i$ 阶的方法总数：

$dp[i]=dp[i-1]+dp[i-2]$

Python3实现：

n = 3

if n==1:
	print (1)
elif n==2:
	print (2)
else:
	pre = 2
	ppre = 1
	times = n-2
	while times:
		times -= 1
		ans = pre + ppre
		ppre = prepre = ans
print (ans)

3.4 斐波那契数列

观察答案序列可知，是一个斐波那契数列，直接套用公式即可，这里不再赘述。