题目描述:
第一次提交:(超时)
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1 or n == 2:
return n
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
方法一:带记忆递归
class Solution(object):
def __init__(self):
self.cache = [1,2]
def climbStairs(self, n):
for i in range(2,n):
self.cache.append(0)
return self.core(n,self.cache)
def core(self, n, r):
if r[n-1] > 0:return r[n-1]
q = self.core(n-1,self.cache)+self.core(n-2,self.cache)
r[n-1] = q
return q
方法二;斐波那契
class Solution:
def climbStairs(self, n: int) -> int:
a, b = 1, 1
for i in range(n):
a, b = b, a + b
return a