Chapter 4 - Dynamic Programming

Dynamic programming can be understood as optimizing sub-problem by decomposing a big problem

Greatest Common Subsequence

What is the greatest common subsequence in two strings A and B?

We can start by answering what is the greatest among A[0] and B[0]? The answer is clear, if A[0] and B[0] are the same, then we increment our answer by 1. What if we have A[0,1] and B[0,1]? And so on we can break this problem into bunch of small problem.

One pseudo-code can be:

function leng(i,j):
    if i or j is 0: //going backward, if i or j reaches the first element, then that means we r done
        return 0
    if A[i] == B[j]: //if they are the same, then just decrement 1 to search for new elements
        1+leng(i-1,j-1)
    else: //if they are different, then take the maximum of i-1 or j-1
        max(leng(i,j-1), leng(i-1,j))

def leng(i,j):
    if i == 0 or j == 0:
        return 0
    if a[i] == a[j]:
        temp = 1 + leng(i-1,j-1)
    else:
        temp = leng(i-1,j)
        temp2 = leng(i,j-1)
        temp = max(temp, temp2)
    return temp

But, the problem here is that this algorithm is too slow, it tries to solve every single possible combination repeatedly. We can incorporate a lookup/hash table so that it doesn't repeat any calculations

look = defaultdict(set)
def leng(i,j):
    if i == 0 or j == 0:
        return 0
    temp = look[i,j]
    if not temp:
        if a[i] == b[j]:
            temp = 1 + leng(i-1,j-1)
        else:
            temp = leng(i-1,j)
            temp2 = leng(i,j-1)
            temp = max(temp, temp2)
        look[i,j] = temp
    return temp

Remember, for each subproblem(i,j) we have (i-1,j), (i,j-1), (i-1,j-1)

Wood Cutting Problem

function best(l)    
    if l = 0
        return 0
    if l > 0
        return max(best(k)+val[k,l]) for 0 <= k < l

look = [float('inf')] * n
decisions = []
def best(l):
    if l == 0:
        return 0
    temp = look[l]
    if temp != float('inf'):
        return temp
    for k in range(0, l-1):
        if best(k) + val[k,l] > temp:
            temp = best(k) + val[k,l]
            rcut = k
    look[l] = temp
    decisions[l] = rcut
    return temp