接外包,有相关需求的可以联系我:Telegram | Email

Fibonacci Number | DpTable | Violent Hacking

该文章创建(更新)于03/16/2022,请注意文章的时效性!

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Solution

Violent Hacking / DP Table

Code

Violent Hacking

O(2^n)

  • submit code
class Solution:
    def fib(self, n: int) -> int:
        if(n == 0):
            return 0
        elif(n == 1):
            return 1
        else:
            return self.fib(n-1) + self.fib(n-2)        
  • full code
class Solution:
    def fib(self, n):
        if(n == 0):
            return 0
        elif(n == 1):
            return 1
        else:
            return self.fib(n-1) + self.fib(n-2)

S = Solution()
print(S.fib(20))

DpTable | Top - Bottom

  • submit code

O(n)

class Solution:
    def fib(self, n: int) -> int:
        # Create a Dp Table
        self.dp = [-1 for x in range(n + 1)]

        return self.dpTable(self.dp,n)

    def dpTable(self,dp,n):
        if (n == 0 or n == 1):
            self.dp[n] = n            
            return n
        # if has f(n) , just return it without calculate
        elif (self.dp[n] != -1):
            return self.dp[n]
        else:
        # if has not f(n),calculate it and put it into dp[n]
            self.dp[n] = self.dpTable(dp,n - 1) + self.dpTable(dp,n - 2)
            return self.dp[n]
  • full code
class Dp_Solution_2:
    def fib(self, n):
        # Create a Dp Table
        self.dp = [-1 for x in range(n + 1)]

        return self.dpTable(self.dp, n)

    def dpTable(self, dp, n):
        if (n == 0 or n == 1):
            self.dp[n] = n
            return n
        # if has f(n) , just return it without calculate
        elif (self.dp[n] != -1):
            return self.dp[n]
        else:
            self.dp[n] = self.dpTable(dp, n - 1) + self.dpTable(dp, n - 2)
            return self.dp[n]

DpS = Dp_Solution_2()
print(DpS.fib(20))

DpTable | Bottom - Top

  • submit code
class Solution:
    def fib(self, n: int) -> int:
        # base case
        if n == 0:
            return 0

        tmp = [-1 for x in range(n+1)]

        tmp[0] = 0
        tmp[1] = 1

        for m in range(2,n+1):
            tmp[m] = tmp[m-1] + tmp[m - 2]

        return tmp[n]
  • full test code
class TopSolution:
    def fib(self,n):
        # base case
        if n == 0:
            return 0

        tmp = [-1 for x in range(n+1)]

        tmp[0] = 0
        tmp[1] = 1

        for m in range(2,n+1):
            tmp[m] = tmp[m-1] + tmp[m - 2]

        return tmp[n]


T = TopSolution()
print(T.fib(20))

Normal Way with less space using

  • submit code
class Solution:
    def fib(self, n: int) -> int:
        # base case
        if n == 0 or n == 1:
            return n

        slow = 0
        fast = 1

        ret = -1

        for m in range(2,n+1):
            ret = slow + fast
            slow = fast
            fast = ret

        return ret
  • full code
class TopSolutionRound:
    def fib(self,n):
        # base case
        if n == 0:
            return 0

        slow = 0
        fast = 1

        for m in range(2,n+1):
            ret = slow + fast
            slow = fast
            fast = ret

        return ret


TR = TopSolutionRound()
print(TR.fib(20))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/03/16/fibonacci-number/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码


阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)