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

In [2]:
fib(10)

Out[2]:
55
In [97]:
fib(11)

Out[97]:
89
In [5]:
fib(2)

Out[5]:
1
In [8]:
def fibMemo(n, mem):
if n<=1: return n
if mem[n]!=None: return mem[n]
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 [9]:
fibFast(100)

Out[9]:
354224848179261915075
In [10]:
fibFast(1000)

Out[10]:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
In [11]:
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 [12]:
fibBottomUp(100)

Out[12]:
354224848179261915075
In [13]:
fibBottomUp(1000)

Out[13]:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
In [14]:
fibBottomUp(1000) == fibFast(1000)

Out[14]:
True
In [15]:
def fibSpaceSave(n):
if n <= 1: return n
mem = [0, 1]
for i in range(2, n+1):
x = mem[0] + mem[1]
mem[0] = mem[1]
mem[1] = x
return mem[1]

In [16]:
fibSpaceSave(100)

Out[16]:
354224848179261915075
In [17]:
fibSpaceSave(1000)

Out[17]:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
In [57]:
G = [
[ [1, 3], [2, 1] ],
[ [3, 7] ],
[ [3, 11] ],
[ [4, 1] ],
[],
[]
]

In [58]:
def reverseGraph(G):
n = len(G)
adj = [ [] for i in range(n) ]
for i in range(n):
for e in G[i]:

In [59]:
reverseGraph(G)

Out[59]:
[[], [[0, 3]], [[0, 1]], [[1, 7], [2, 11]], [[3, 1]], []]
In [62]:
def shortestDAGMemo(revG, s, t, mem):
if t==s: 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]:
mem[t] = min(mem[t], shortestDAGMemo(revG, s, e[0], mem) + e[1])
return mem[t]

def shortestDAG(G, s, t):
mem = [None]*len(G)
return shortestDAGMemo(reverseGraph(G), s, t, mem)


In [9]:
shortestDAG(G, 0, 1)

Out[9]:
3
In [10]:
shortestDAG(G, 0, 5)

Out[10]:
inf
In [11]:
shortestDAG(G, 0, 3)

Out[11]:
10
In [12]:
def genBad(n):
# produces a bad graph with 3n+1 vertices
adj = [ [] for _ in range(3*n+1) ]
for i in range(n):
adj[3*i]   += [ [3*i+1, 1], [3*i+2, 1] ]
adj[3*i+1] += [ [3*i+3, 1] ]
adj[3*i+2] += [ [3*i+3, 1] ]

In [13]:
genBad(5)

Out[13]:
[[[1, 1], [2, 1]],
[[3, 1]],
[[3, 1]],
[[4, 1], [5, 1]],
[[6, 1]],
[[6, 1]],
[[7, 1], [8, 1]],
[[9, 1]],
[[9, 1]],
[[10, 1], [11, 1]],
[[12, 1]],
[[12, 1]],
[[13, 1], [14, 1]],
[[15, 1]],
[[15, 1]],
[]]
In [14]:
shortestDAG(genBad(5), 0, 3*5)

Out[14]:
10
In [15]:
m = 21

Out[15]:
42
In [16]:
def findShortestDAGMemo(revG, s, t, mem, choices):
if t==s: 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]:
tmp = findShortestDAGMemo(revG, s, e[0], mem, choices)
if tmp + e[1] < mem[t]:
mem[t] = tmp + e[1]
choices[t] = e[0]
return mem[t]

def findShortestDAG(G, s, t):
mem = [None]*len(G)
choices = [None]*len(G)
distance = findShortestDAGMemo(reverseGraph(G), s, t, mem, choices)
if distance == float('infinity'):
return [distance, []]
if s==t: return [0, []]
path = [t]
at = t
while at!=s:
path.append(choices[at])
at = choices[at]
path.reverse()
return [distance, path]

In [17]:
findShortestDAG(G, 0, 4)

Out[17]:
[11, [0, 1, 3, 4]]
In [3]:
# return LIS of L[i..n] in which all numbers must be bigger than L[last]
def lisRecurse(L, last, i):
if i == len(L): return 0
elif L[i]<L[last]: return lisRecurse(L, last, i+1)
else: return max(lisRecurse(L, last, i+1), 1 + lisRecurse(L, i, i+1))

def lis(L):
return lisRecurse([-float('infinity')] + L, 0, 1)

In [8]:
lis(list(range(24)))

Out[8]:
24
In [15]:
# return LIS of L[i..n] in which all numbers must be bigger than L[last]
def lisRecurseMemo(L, last, i, mem):
if i == len(L): return 0
elif mem[last][i] != None: return mem[last][i]
elif L[i]<L[last]:
mem[last][i] = lisRecurseMemo(L, last, i+1, mem)
return mem[last][i]
else:
mem[last][i] = max(lisRecurseMemo(L, last, i+1, mem),
1 + lisRecurseMemo(L, i, i+1, mem))
return mem[last][i]

def lisMemo(L):
mem = [[None]*(1+len(L)) for _ in range(len(L)+1)]
return lisRecurseMemo([-float('infinity')] + L, 0, 1, mem)

In [17]:
lisMemo(list(range(400)))

Out[17]:
400
In [1]:
def lisBottomUp(L):
L = [-float('infinity')] + L
n = len(L)
# mem[last][i] gives us f(last, i)
mem = [[None]*(n+1) for _ in range(n)]
# fill in base cases
for last in range(n):
mem[last][n] = 0
for i in range(n-1, -1, -1):
for last in range(n):
if L[i] <= L[last]:
mem[last][i] = mem[last][i+1]
else:
mem[last][i] = max(mem[last][i+1], 1 + mem[i][i+1])
return mem[0][1]

In [16]:
lisBottomUp([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])

Out[16]:
6
In [17]:
def lisBottomUpSaveSpace(L):
# use 2n extra memory instead of n^2; just remember last two rows of mem table
L = [-float('infinity')] + L
n = len(L)
prev = [0]*n # base cases, prev[last] = f(last ,n)
for i in range(n-1, 0, -1): # go from i=n-1 down to i=1
cur = [0]*n
for last in range(n):
if L[i] <= L[last]:
cur[last] = prev[last]
else:
cur[last] = max(prev[last], 1 + prev[i])
# now move over everything in cur to prev before we process the next i
for last in range(n):
prev[last] = cur[last]

return cur[0] # returns f(0, 1)

In [18]:
lisBottomUpSaveSpace([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])

Out[18]:
6
In [6]:
# return LIS of L[i..n] in which all numbers must be bigger than L[last]
def lisRecurseMemoWithSolution(L, last, i, mem, choices):
if i == len(L): return 0
elif mem[last][i] != None: return mem[last][i]
elif L[i]<L[last]:
mem[last][i] = lisRecurseMemoWithSolution(L, last, i+1, mem, choices)
choices[last][i] = 'skip'
return mem[last][i]
else:
A = lisRecurseMemoWithSolution(L, last, i+1, mem, choices)
B = 1 + lisRecurseMemoWithSolution(L, i, i+1, mem, choices)
if A > B:
choices[last][i] = 'skip'
mem[last][i] = A
else:
choices[last][i] = 'take'
mem[last][i] = B
return mem[last][i]

# return the actual subsequence which is longest, and not just its length
def lisMemoWithSolution(L):
mem = [[None]*(1+len(L)) for _ in range(len(L)+1)]
choices = [[None]*(1+len(L)) for _ in range(len(L)+1)]
L = [-float('infinity')] + L
lisRecurseMemoWithSolution(L, 0, 1, mem, choices)
cur_last = 0
cur_i = 1
ans = []
while cur_i != len(L):
if choices[cur_last][cur_i] == 'take':
ans.append(L[cur_i])
cur_last = cur_i
cur_i += 1
return ans

In [8]:
lisMemoWithSolution([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])

Out[8]:
[0, 4, 6, 9, 13, 15]

# Now here are some more examples with just the recursion written. Try to write memoized versions, bottom-up versions, and bottom-up space saving versions (if possible) yourself as practice! Or versions that reconstruct an actual optimal solution and not just the cost.¶

In [34]:
def editDistanceRecurse(s, t, i, j):
# compute edit distance of s[i..n], t[j..m]
n = len(s)
m = len(t)
if i == n: return m-j
elif j==m: return n-i
else:
# since we have to turn s into t, we have to in particular make the first letter
# of s match t, either via prepending t[j], deleting s[i], or substituting
A = 1 + editDistanceRecurse(s, t, i, j+1) # insert t[j] before s[i]
B = 1 + editDistanceRecurse(s, t, i+1, j) # delete s[i]
C = editDistanceRecurse(s, t, i+1, j+1) # substitution
if s[i] != t[j]:
C += 1
return min(min(A, B), C)

def editDistance(s, t):
return editDistanceRecurse(s, t, 0, 0)

In [35]:
editDistance('kitten', 'sitting')

Out[35]:
3
In [40]:
def knapsackRecurse(L, w, i):
# max value we can pack amongst items L[i..n] with knapsack of capacity w
# each item in L is a pair (weight, value)
if i==len(L): return 0
elif L[i][0] > w: return knapsackRecurse(L, w, i+1)
else:
return max(knapsackRecurse(L, w, i+1),
L[i][1] + knapsackRecurse(L, w-L[i][0], i+1))

def knapsack(L, W):
# max value of items we can pack in capacity-W knapsack
return knapsackRecurse(L, W, 0)

In [41]:
knapsack([ [11,15], [10, 10], [10,10] ], 20)

Out[41]:
20
In [48]:
def matrixChainMultRecurse(lengths, a, b):
# compute cheapest parenthesization to multiply lengths[a..b]
if a==b: return 0
# loop over which multiplication will be the last one
ans = float('infinity')
for i in range(a, b):
ans = min(ans, matrixChainMultRecurse(lengths, a, i)
+ matrixChainMultRecurse(lengths, i+1, b)
+ lengths[a][0]*lengths[i][1]*lengths[b][1])
return ans

def matrixChainMult(lengths):
# need to multiply A_1 x A_2 x ... x A_n
# but can choose the parenthesization. Parenthesize so as to take the least total time,
# where multiplying an
return matrixChainMultRecurse(lengths, 0, len(lengths) - 1)

In [74]:
matrixChainMult([ [3,3], [3,2], [2,1] ])

Out[74]:
15
In [55]:
def shortestPathRecurse(revG, s, t, k):
# find shortest path from s to t using at most k edges
if k == 0:
if t==s: return 0
else: return float('infinity')
else:
ans = shortestPathRecurse(revG, s, t, k-1)
for e in revG[t]:
ans = min(ans, e[1] + shortestPathRecurse(revG, s, e[0], k-1))
return ans

def shortestPath(G, s, t):
return shortestPathRecurse(reverseGraph(G), s, t, len(G)-1)

In [63]:
shortestPath(G, 0, 3) == shortestDAG(G, 0, 3)

Out[63]:
True
In [65]:
def APSPrecurse(A, i, j, k):
# length of shortest path from i to j when all intermediate vertices can only be in the
# set {1,...,k}
if k == 0: return A[i][j]
else:
return min(APSPrecurse(A, i, j, k-1),
APSPrecurse(A, i, k, k-1) + APSPrecurse(A, k, j, k-1))

def APSP(A, i, j):
return APSPrecurse(A, i, j, len(A)-1)

In [70]:
def convertToAdjMatrix(G):
n = len(G)
A = [[float('infinity')]*n for _ in range(n)]
for i in range(len(G)):
for e in G[i]:
A[i][e[0]] = e[1]
return A

In [71]:
shortestPath(G, 0, 3) == APSP(convertToAdjMatrix(G), 0, 3)

Out[71]:
True
In [72]:
# A is the adjacency matrix with weights
def TSPrecurse(A, at, S):
# have already visited all vertices in S, which is a bitvector
n = len(A)
if S == (1<<n)-1: return 0
else:
ans = float('infinity')
for i in range(n):
if S & (1<<i) == 0:
ans = min(ans, A[at][i] + TSPrecurse(A, i, S|(1<<i)))
return ans
def TSP(A):
# find the shortest route starting at 0 which visits all vertices
return TSPrecurse(A, 0, 1)

In [73]:
TSP([ [1,1], [1,1] ])

Out[73]:
1
In [ ]: