-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathdynamic_programming.py
More file actions
65 lines (61 loc) · 1.81 KB
/
Copy pathdynamic_programming.py
File metadata and controls
65 lines (61 loc) · 1.81 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# dynamic programming
# using recursion function would usually take O(2^n) time but if we use the memo function it will take O(n) time just like the bottom up solution
# A memoized solution
def fib_2(n, memo):
if memo[n] is not None:
return memo[n]
if n == 1 or n == 2:
result = 1
else:
result = fib_2(n-1, memo) + fib_2(n-2, memo)
memo[n] = result
return result
def fib_memo(n):
memo = [None] * (n + 1)
return fib_2(n, memo)
____________________________________________________________________________________________________________________________________
# Create a memoisation decorator
def memoise(f):
memo = {}
def checker(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return checker
# And apply it! Done!
@memoise
def fib(num):
if num == 0:
return 0
elif num == 1:
return 1
else:
return fib(num - 1) + fib(num - 2)
________________________________________________________________________________________________________________________________
class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, *args):
if args not in self.memo:
self.memo[args] = self.fn(*args)
return self.memo[args]
@Memoize
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
_______________________________________________________________________________________________________________________________
# A bottom-up solution
def fib_bottom_up(n):
if n == 1 or n == 2:
return 1
bottom_up = [None] * (n+1)
bottom_up[1] = 1
bottom_up[2] = 1
for i in range(3, n+1):
bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
return bottom_up[n]