假设你正在爬楼梯。需要 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级台阶，可以从n-1跨一步，或者n-2一次跨两步，直接加和；
2）斐波拉契最直观的解法，是用递归，但递归方法计算量大，改进为动态规划问题，即将前面计算过的存起来，避免重复计算。
代码示例
def climbStairs(self, n: int) -> int:
lst = [1, 2]
if n < 3:
return lst[n-1]
for i in range(3, n+1):
lst.append(lst[i-2] + lst[i-3])
return lst[-1]
print(climbStairs(3))
执行用时：28 ms, 在所有 Python3 提交中击败了 96.87% 的用户.
本文为 陈华 原创，欢迎转载，但请注明出处：http://www.ichenhua.cn/read/365
