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