爬楼梯

爬楼梯

九月 02, 2021

爬楼梯

递归（×

写了半天递归结果超时了。。抓狂

不过既然f(n) = f(n - 1) + f(n - 2) 那我们就可以去计算它的通项公式

最后是得到这样的结果 所以可以直接通过公式算出结果

动态规划

我们需要一个数组来储存所有的结果

所以

1
2
3
4
5
6
7
8
class Solution(object):
    def climbStairs(self,n):
        store = []
        store.append(1)
        store.append(1)
        for x in range(2,n+1):
            store.append(store[x-1] + store[x-2])
        return store[n]