该文章创建(更新)于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.

• https://leetcode.com/problems/fibonacci-number/

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))

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin