解答
1.递归法
最后一次计算分两种情况：最后一次上一级台阶，或者最后一次上两级台阶。
所以f(n)=f(n-1)+f(n-2)
f(n-1)是最后一次上一级台阶，即第n-1阶到第n阶，在最后一次上台阶之前的次数和；f(n-2)是最后一次上两级台阶，即第n-2阶到第n阶，在最后一次上台阶之前的次数和。
class Solution(object):
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
# 在类中调用函数要加self
2.动态规划
说实话感觉动态规划和递归很像啊，我有点分不清楚....为啥动态规划就很快呢？
解答：动态规划其实也是将原问题分解为子问题，然后递归地求解子问题。由于子问题会有重叠，所以将每个求出的子问题的解存储起来，当下次再求解这个子问题时直接拿来用。多就多在它可以记忆化存储。
思路和递归一样，用最后一阶台阶的前一步来分析
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
result = [1,2]
for i in range(2, n):
result.append(result[i-1]+result[i-2])
return result[-1]
标准写法：先初始化dp
class Solution:
def climbStairs(self, n: int) -> int:
if n <=2:
return n
dp = [0] * (n+1) # 申请存储空间index为[0,1,2...n]
# dp=[0]*n也可以，那么dp[0]即n=1的方法数.
# 如果dp=[0]*n+1，则dp[0]不考虑
dp[1] = 1
dp[2] = 2 # dp=[0,1,2,0,0...0]
# 从n=3开始f(n)=f(n-1)+f(n-2)
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
3.斐波那契公式
斐波那契数列的模型为f0 = 1,f1 = 1,f2 = 2, fn+2 = fn+1 + fn
满足这种情况的题目可以使用斐波那契公式。
斐波那契公式
具体介绍来自：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode/
将n带入公式就可以得知最后的解。
import math
class Solution:
def climbStairs(self, n: int) -> int:
sqrt5=math.sqrt(5);
fibn=pow((1+sqrt5)/2,n+1)-pow((1-sqrt5)/2,n+1);
return int(fibn/sqrt5);
