Solution to LeetCode 509 Fibonacci Number, LeetCode 1137 N-th Tribonacci Number, and JZ 10 Fibonacci number.
LeetCode 509
Fibonacci Number (Easy). [link]
1] Recursion without memorization. Time complexity O(2^n). Space complexity O(n).
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
return n if n <= 1 else self.fib(n-1) + self.fib(n-2)
Since the answers to the subproblems are not memorized, this is slow and probably will have TLE.
2] Recursion with memoization. Time complexity O(n). Space complexity O(n).
A simple way to implement recursion with memoization is by @cache
class Solution(object):
@cache
def fib(self, n):
"""
:type n: int
:rtype: int
"""
return n if n <= 1 else self.fib(n-1) + self.fib(n-2)
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
def fibonacci(n, dp):
if n == 0 or n == 1: return n
if dp[n] != 0: return dp[n]
dp[n] = fibonacci(n-1, dp) + fibonacci(n-2, dp)
return dp[n]
dp = [0] * (n+1)
return fibonacci(n, dp)
3] Dynamic Programming. Time complexity O(n). Space complexity O(n).
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0: return 0
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
4] Dynamic Programming with rolling array. Time complexity O(n). Space complexity O(1).
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
LeetCode 1137
N-th Tribonacci Number (Easy). [link]
class Solution(object):
def tribonacci(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0: return 0
if n <= 2: return 1
dp = [0] * (n+1)
dp[1], dp[2] = 1,1
for i in range(3,n+1):
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
return dp[n]
JZ 10
Fibonacci number (Easy). [link]
Dynamic programming with rolling array, accounting for large number n. Time complexity O(n), space complexity O(1).
class Solution:
def Fibonacci(self , n: int) -> int:
a, b = 0, 1
for i in range(n):
a, b = b, (a + b) % 1000000007
return a
