In [1]:
def fib(n):
if n<=1:
return n
else:
return fib(n-1) + fib(n-2)

In [1]:
# fib(40) # beware of running this line; it'll hang for a while!

In [3]:
def fibMemo(n, mem):
if n<=1:
return n
elif mem[n]!=None:
return mem[n]
else:
mem[n] = fibMemo(n-1,mem) + fibMemo(n-2,mem)
return mem[n]

def fibFast(n):
mem = [None]*(n+1)
return fibMemo(n, mem)

In [4]:
fibFast(40)

Out[4]:
102334155
In [5]:
fibFast(100)

Out[5]:
354224848179261915075
In [6]:
def fibBottomUp(n):
mem = [None]*(n+1)
mem[0] = 0
mem[1] = 1
for i in range(2, n+1):
mem[i] = mem[i-1] + mem[i-2]
return mem[n]

In [7]:
fibBottomUp(40)

Out[7]:
102334155
In [8]:
def fibBottomUpSpaceSaving(n):
mem = [0, 1] # stores mem[i-1] and mem[i-2]
for i in range(2, n+1):
x = mem[0] + mem[1]
mem[0] = mem[1]
mem[1] = x
return mem[1]

In [9]:
fibBottomUpSpaceSaving(40)

Out[9]:
102334155
In [10]:
myG = [ [[1, 3], [2, 1]],
[[3, 1]],
[[3, 11]],
[[4, 1]],
[],
[]]

In [11]:
def revGraph(G):
revG = [ [] for _ in range(len(G))]
for i in range(len(G)):
for e in G[i]:
v = e[0]
weight = e[1]
revG[v].append([i, weight])
return revG

In [12]:
def sPDAGHelper(revG, s, t):
if s==t:
return 0
elif len(revG[t])==0:
return float('infinity')
else:
best = float('infinity')
for e in revG[t]:
v = e[0]
weight = e[1]
best = min(best, sPDAGHelper(revG, s, v) + weight)
return best

def shortestPathDAG(G, s, t):
return sPDAGHelper(revGraph(G), s, t)

In [13]:
shortestPathDAG(myG, 0, 3)

Out[13]:
4
In [14]:
def sPDAGHelperFast(revG, s, t, mem):
if s==t:
return 0
elif len(revG[t])==0:
return float('infinity')
elif mem[t]!=None:
return mem[t]
else:
mem[t] = float('infinity')
for e in revG[t]:
v = e[0]
weight = e[1]
mem[t] = min(mem[t], sPDAGHelperFast(revG, s, v, mem) + weight)
return mem[t]

def shortestPathDAGFast(G, s, t):
mem = [None]*len(G)
return sPDAGHelperFast(revGraph(G), s, t, mem)

In [15]:
shortestPathDAGFast(myG, 0, 3)

Out[15]:
4
In [16]:
def sPDAGHelperGetPath(revG, s, t, mem, choices):
if s==t:
return 0
elif len(revG[t])==0:
return float('infinity')
elif mem[t]!=None:
return mem[t]
else:
mem[t] = float('infinity')
for e in revG[t]:
v = e[0]
weight = e[1]
x = sPDAGHelperGetPath(revG, s, v, mem, choices) + weight
if x < mem[t]:
choices[t] = v
mem[t] = x
return mem[t]

def shortestPathDAGGetPath(G, s, t):
mem = [None]*len(G)
choices = [None]*len(G)
cost = sPDAGHelperGetPath(revGraph(G), s, t, mem, choices)
if cost == float('infinity'):
return []
path = [t]
at = t
while at != s:
at = choices[at]
path.append(at)
path.reverse()
return path

In [17]:
shortestPathDAGGetPath(myG, 0, 3)

Out[17]:
[0, 1, 3]
In [5]:
# return lis length of B[i..] when all elts chosen must be > B[last]
def lisMemoHelper(i, last, B, mem):
if i == len(B):
return 0
elif mem[i][last] != None:
return mem[i][last]
mem[i][last] = lisMemoHelper(i+1, last, B, mem)
if B[i] > B[last]:
mem[i][last] = max(mem[i][last], 1 + lisMemoHelper(i+1, i, B, mem))
return mem[i][last]

def lisMemo(A):
B = [-float('infinity')] + A # sentinel !
mem = [[None]*len(B) for _ in range(len(B))]
return lisMemoHelper(1, 0, B, mem)

In [6]:
lisMemo([1,7,2,3])

Out[6]:
3
In [9]:
def lisBottomUp(A):
B = [-float('infinity')] + A
n = len(B)
mem = [[None]*n for _ in range(n+1)]
for last in range(n):
mem[n][last] = 0
for i in range(n-1, -1, -1): # goes from n-1 down to 0
for last in range(n):
mem[i][last] = mem[i+1][last]
if B[i] > B[last]:
mem[i][last] = max(mem[i][last], 1 + mem[i+1][i])
return mem[1][0]

In [10]:
lisBottomUp([1,7,2,3])

Out[10]:
3
In [11]:
# f(i, *) only depends on f(i+1, *), so only need to track two rows at a time; O(n) space instead of O(n^2)
def lisBottomUpSpaceSaving(A):
B = [-float('infinity')] + A
n = len(B)
mem = [[None]*n for _ in range(2)]
for last in range(n):
mem[0][last] = 0
for i in range(n-1, -1, -1): # goes from n-1 down to 0
for last in range(n):
mem[1][last] = mem[0][last]
if B[i] > B[last]:
mem[1][last] = max(mem[1][last], 1 + mem[0][i])
for last in range(n):
mem[0][last] = mem[1][last]
return mem[1][0]

In [12]:
lisBottomUpSpaceSaving([1,7,2,3])

Out[12]:
3
In [13]:
# return max value from packing A[i..] when knapsack can only fit weight C
def knapsackMemoHelper(i, C, A, mem):
if i == len(A):
return 0
elif mem[i][C] != None:
return mem[i][C]
else:
mem[i][C] = knapsackMemoHelper(i+1, C, A, mem)
if A[i][0] <= C:
mem[i][C] = max(mem[i][C], A[i][1] + knapsackMemoHelper(i+1, C-A[i][0], A, mem))
return mem[i][C]

def knapsackMemo(A, W): # elts of A are [weight, val] pairs
mem = [[None]*(W+1) for _ in range(len(A))]
return knapsackMemoHelper(0, W, A, mem)

In [14]:
knapsackMemo([[11,15], [10,10], [10,10]], 20) # should take the last two items and not the first

Out[14]:
20
In [17]:
# f(i, S) = min travel distance to hit every loc in S when starting at i
def tspMemoHelper(i, S, D, mem):
if S == 0:
return 0
elif mem[i][S] != None:
return mem[i][S]
else:
mem[i][S] = float('infinity')
for x in range(len(D)):
if (S & (1<<x)) != 0:
mem[i][S] = min(mem[i][S], D[i][x] + tspMemoHelper(x, S^(1<<x), D, mem))
return mem[i][S]

# minimum total distance starting from 0 to visit all other locations
def travelingSalesmanMemo(D): # D[i][j] is distance from location i to j; assume it's a metric
mem = [[None]*(2**len(D)) for _ in range(len(D))]
return tspMemoHelper(0, (2**len(D))-2, D, mem) # need to visit 1,2,3...,n-1, rep'd by 2^n - 2

In [19]:
# 3 points 0,1,2 where dist from 0 to 2 is 2, and otherwise pairwise dists are all 1
# best route is 0->1->2 with cost 2 (0->2->1 would cost 3)
travelingSalesmanMemo([[0,1,2], [1,0,1], [2,1,0]])

Out[19]:
2
In [23]:
# f(i,j) = min cost to multiply A_i x ... x A_j
def mcmMemoHelper(i, j, s, mem):
if i == j:
return 0
elif mem[i][j] != None:
return mem[i][j]
else:
mem[i][j] = float('infinity')
for k in range(i, j):
# try the last multiplication being b/w (A_i x .. x A_k) and (A_{k+1} x .. x A_j)
mem[i][j] = min(mem[i][j],
s[i]*s[k+1]*s[j+1] + mcmMemoHelper(i, k, s, mem) + mcmMemoHelper(k+1, j, s, mem))
return mem[i][j]

# multiply A_1 x ... x A_n where A_i is an s[i] x s[i+1] matrix
def matrixChainMultMemo(s):
mem = [[None]*(len(s)-1) for _ in range(len(s)-1)]
return mcmMemoHelper(0, len(s)-2, s, mem)

In [24]:
# example from class: A x B x C where A is 3x3, B is 3x2, C is 2x1; Ax(BxC) is cheaper than (AxB)xC
matrixChainMultMemo([3, 3, 2, 1])

Out[24]:
15