Fibonacci Number | DpTable | Violent Hacking

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

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2022/03/16/fibonacci-number/``

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安