Python刷leetcode--剑指 Offer 10- II.青蛙跳台阶问题

109 阅读 0 评论 72 点赞

我是靠谱客的博主直率水杯，这篇文章主要介绍Python刷leetcode--剑指 Offer 10- II.青蛙跳台阶问题，现在分享给大家，希望可以做个参考。

思路：先递归，再优化递归。

拖慢递归的原因是重复的底层计算。所以计算过一次就存起来。每次计算就判断是不是已经计算过了

当然也可以往斐波那契数列上想，因为形式都跟它一摸一样，应该也可以迭代着写。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def __init__(self):
        self.val = {}
        self.count = 0

    def numWays(self, n: int) -> int:
        # leetcode submit region end(Prohibit modification and deletion)
        return self.rec(n) % 1000000007

    def rec(self, n):
        if n == 1 or n == 0:
            return 1
        if n - 1 in self.val:
            a = self.val.get(n - 1)
        else:
            self.count += 1
            a = self.rec(n - 1)
            self.val[n - 1] = a
        if n - 2 in self.val:
            b = self.val.get(n - 2)
        else:
            self.count += 1
            b = self.rec(n - 2)
            self.val[n - 2] = b
        return a + b


if __name__ == '__main__':
    sol = Solution()
    print(sol.numWays(7))
    print(sol.count)