blob: 9c6b4fda4cc435a0c47372b232308d66e33f5a93 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# fibonacci
# time complexity: O(n^2)
# space complexity: O(n)
def fib(n):
return 1 if n <= 2 else fib(n - 1) + fib(n - 2)
# memoization
# time complexity: O(n)
# space complexity: O(n)
def fib_memo(n, memo={}):
if n <= 2:
return 1
if n in memo:
result = memo[n]
result = fib_memo(n - 1, memo[n]) + fib_memo(n - 2, memo[n])
return result
|
