博客

一开始想的很简单，直接用递归

class Solution:
    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)

这样写直接就提示超出时间限制了，只能计算到37，38开始就超出时间限制



后来就去学习了一下记忆性递归，将值存在数组中

比如说climbmemo(n-1,memo)已经将climbmemo(n-2,memo)都覆盖到了，那后面只需在数组中找到该值返回即可，不用再去计算一遍

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = [0]*(n+1)
        #a = self.climbmemo(n,memo)
        #return a
        return self.climbmemo(n,memo) #调用climbmemo()函数
    def climbmemo(self,n,memo):
        if memo[n] > 0:   #memo[n] > 0表示数组中已经有这个值了，不用再去计算，直接返回即可
            return memo[n]  
        if n == 1:
            memo[n] = 1
        elif n == 2:
            memo[n] = 2
        else:
            memo[n] = self.climbmemo(n-1,memo)+self.climbmemo(n-2,memo)
        return memo[n]

还有一种简单写法如下，属于动态规划的思想，但又太简单，不能算是动态规划？

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        a = 1
        b = 2
        for i in range(3, n+1):
            tmp = a+b
            a=b
            b=tmp
        return tmp