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]:
            adj[e[0]] += [ [i, e[1]]]
    return adj
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] ]
    return adj
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
shortestDAG(genBad(m), 0, 3*m)
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 [ ]: