climb_statirs

  • 2022-12-14
  • 浏览 (545)

climb_statirs.py 源码

# 爬楼梯


class Solution:
    # 递归
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

    # 递归+备忘录
    def climbStairs2(self, n: int) -> int:

        def helper(x: int) -> int:
            if x <= 2:
                return x
            if x in mem:
                return mem[x]
            res = helper(x - 1) + helper(x - 2)
            mem[x] = res
            return res
        mem = {}
        return helper(n)

    # 动态规划
    def climbStairs3(self, n: int) -> int:
        front, back = 0, 1
        for _ in range(n):
            front, back = back, front + back
        return back

你可能感兴趣的文章

best_time_buy_sell_stock

best_time_buy_sell_stock_ii

container_with_most_water

0  赞