斐波那契数

╰+哭是因爲堅強的太久メ 2022-06-08 02:46 135阅读 0赞

> 牛客网 《剑指offer》

时间限制：`1秒` 空间限制：`32768K` 热度指数：`199742`

**解题思路**

一：  
如果像这样，将会有大量的计算是重复的，时空复杂度过大  
![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

二：  
可以考虑将计算过的结果缓存起来，如果发现一个 `n` 已经计算过了，就不再重复计算

三：  
非递归解法，即从下往上算  
首先根据 `f(0)`和 `f(1)` 算出 `f(2)`，再根据`f(1)` 和 `f(2)`算出`f(3)`。。。以此类推

python 2.7  
递归

# -*- coding:utf-8 -*-
    class Solution:
        def __init__(self):
            self.dic = {
       0:0, 1:1}
    
        def Fibonacci(self, n):
            # write code here
            if n < 0:
                return None
            if self.dic.has_key(n):
                return self.dic[n]
            m1 = self.getF(n - 1)
            if not m1:
                m1 = self.Fibonacci(n - 1)
                self.dic[n - 1] = m1
    
            m2 = self.getF(n - 2)
            if not m2:
                m2 = self.Fibonacci(n - 2)
                self.dic[n - 2] = m2
            return m1 + m2 
    
        def getF(self, n):
            if self.dic.has_key(n):
                return self.dic[n]
            return None

运行时间：28ms
    占用内存：5768k

> [https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97.py][https_github.com_Jack-Lee-Hiter_AlgorithmsByPython_blob_master_Target_20Offer_E6_96_90_E6_B3_A2_E9_82_A3_E5_A5_91_E6_95_B0_E5_88_97.py]

''' 题目一：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39 题目二：一只青蛙一次可以跳上一级台阶，也可以跳上两级台阶，问该青蛙跳上一个 n 级台阶有多少种跳法？ 题目三：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 解法参见牛客网讨论：https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387 '''
    
    # -*- coding:utf-8 -*-
    class Solution:
        def Fibonacci(self, n):
            tempArray = [0, 1]
            if n >= 2:
                for i in range(2, n+1):
                    tempArray[i%2] = tempArray[0] + tempArray[1]
            return tempArray[n%2]
        # 青蛙跳台阶, 每次可以跳1级或2级
        def jumpFloor(self, number):
            # write code here
            tempArray = [1, 2]
            if number >= 3:
                for i in range(3, number + 1):
                    tempArray[(i + 1) % 2] = tempArray[0] + tempArray[1]
            return tempArray[(number + 1) % 2]
    
        def jumpFloorII(self, number):
            ans = 1
            if number >= 2:
                for i in range(number-1):
                    ans = ans * 2
            return ans
    
    test = Solution()
    print(test.Fibonacci(100))
    print(test.jumpFloor(3))
    print(test.jumpFloorII(2))

[SouthEast]: /images/20220608/391733c7248b4c05a95f7babc5e4d905.png
[SouthEast 1]: /images/20220608/15d664439272498f833f9fffc7bbe178.png
[https_github.com_Jack-Lee-Hiter_AlgorithmsByPython_blob_master_Target_20Offer_E6_96_90_E6_B3_A2_E9_82_A3_E5_A5_91_E6_95_B0_E5_88_97.py]: https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97.py