【剑指 Offer 10- II. 青蛙跳台阶问题】【力扣刷题】【Python】【动态规划】

最新推荐文章于 2024-07-18 01:47:57 发布

☀️오동동

最新推荐文章于 2024-07-18 01:47:57 发布

阅读量292

点赞数

分类专栏：剑指offer

本文链接：https://blog.csdn.net/TongWu1/article/details/109622318

版权

剑指offer 专栏收录该内容

19 篇文章

订阅专栏

我的想法：斐波那契

代码就不写了和昨天一样，不过我一开始没找到递归表达式，他是要考虑最后一次跳时不是一个台阶就是两个台阶。
递归方法

class Solution:
    def numWays(self, n: int) -> int:
        while n>=0:
            if n==1 or n==0:
                return 1
            elif n==2:
                return 2
            else:
                return self.numWays(n-1)+self.numWays(n-2)

递归方法的优化：把计算过的数存储起来。
依旧会超出时间限制

class Solution:
    def numWays(self, n: int) -> int:
        dic={}
        while n>=0:
            if n==1 or n==0:
                return 1
            elif n==2:
                return 2
            if dic.get(n):
                return dic.get(n)
            sumNum=self.numWays(n-1)+self.numWays(n-2)
            dic[n]=sumNum
            return sumNum

详细可以参考青蛙跳台阶
动态规划的方法是我初次接触到，我明天学吧。

11月12日更新

大概了解了动态规划，接下来从动态规划问题开始练习巩固动态规划

class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007