Dynamic Programming#

Dynamic algorithms are a family of programs which (broadly speaking) share the feature of utilising solutions to subproblems in coming up with an optimal solution. We will discuss the conditions which problems need to satisfy to be solved dynamically but let us first have a look at some basic examples. The concept is quite challenging to digest, so there are many examples in this section.

Simple Examples#

  • Dynamic Fibonacci If you have read the section about recursion you probably know that the basic implementation for generating Fibonacci numbers is very inefficient (\(O(2^n)\)!). Now, as we generate the next numbers in the Fibonacci sequence, we will remember them for further use. The trade-off between memory and time is dramatic in this case. Compare the two versions of the function:

# For comparing the running times
import time

# Inefficient
def fib(n):
    assert n >= 0
    if n < 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
    
# Dynamic version
def dynamicFib(n):
    assert n >= 0
    #prepare a table for memoizing
    prevFib = 1
    prevPrevFib = 1
    temp = 0

    #build up on your previous results
    for i in range(2,n+1):
        temp = prevFib + prevPrevFib
        prevPrevFib = prevFib
        prevFib = temp
    return prevFib
    
start = time.time()
print(fib(32))
end = time.time()
print("Time for brute:" + str(end - start))

start = time.time()
print(dynamicFib(32))
end = time.time()
print("Time for dynamic:" + str(end - start))
3524578
Time for brute:0.8238296508789062
3524578
Time for dynamic:0.0

The time difference is enormous! As you can probably spot, dynamicFib is \(O(n)\)! With the use of three integer variables (prevFib, prevPrevFib and temp) we brought exponential time complexity down to linear. How did it happen? Let us now depict the work done by fib(5) on a graph:

../../_images/FibTree.png

Wow! This is quite a tree! However, the worst feature is that many of the nodes are repeated (e.g. node \(2\) appears 3 times). These repeated results which are constantly recomputed bring us to the exponential complexity. Consider the dynamic solution graph:

../../_images/FibDyn.png

Now, the number of nodes grows linearly with \(n\). We have merged the subproblems to avoid redundancy.


  • Shortest Path on a Grid Dynamic programming is often used for optimisation problems. Consider a square grid with numbers from 0 to 9 in each square. An example would be:

+-+-+-+-+
|1|0|8|4| 
+-+-+-+-+
|3|5|1|0|
+-+-+-+-+
|6|8|9|3|
+-+-+-+-+
|1|2|4|5|
+-+-+-+-+

It is allowed to move only down or right. What is the value of the minimum path from the upper-left corner to the lower-right corner?

The initial approach to the problem might be to check all the possible paths and return the minimal one. This is exponential and too slow. To come up with a faster approach we need to find subproblems.

Let us imagine that we have reached the lower-right corner (hurray!). We could get there from the tile above it and left of it. This might at first seem like a Divide and Conquer problem, but let us keep on looking for an overlap:

../../_images/DownRightGrid.png

In the simplest case of four tiles, we can already see that the upper-left tile is considered twice. We should then leverage this repetition. This overlapping generalises for larger grids. In our algorithm, we will remember the optimal path to the tiles already visited and build on this knowledge:

# grid is a square matrix
def shortestPathDownRight(grid):
    # dictionary that will keep the optimal paths 
    # to the already visited tiles
    table = {}
    # n - length of the side of the square
    n = len(grid)
    assert n == 0 or len(grid[0]) == n
    table[(0,0)] = grid[0][0]
    # top and most left column have trival optimal paths
    for i in range(1, n):
        table[(0,i)] = table[(0,i-1)] + grid[0][i]
        table[(i,0)] = table[(i-1,0)] + grid[i][0]
    # the dynamic magic    
    for i in range(1,n):
        for j in range(1,n):
            table[(i,j)] = min(table[(i-1,j)],table[(i,j-1)]) + grid[i][j]
            
    return table[(n-1,n-1)]

grid = [[1,0,8,4],[3,5,1,0],[6,8,9,3],[1,2,4,5]]
print(shortestPathDownRight(grid))
15

What is the time complexity of this algorithm? Based on the nested loop we can deduce that it is \(O(n^2)\). Quite an improvement!


Space Complexity#

We usually do not concern ourselves with the amount of memory a program utilises. Dynamic programs are an exception to this rule. The amount of memory they use can be a limiting factor for some machines, so we need to take it into account. In the case of dynamicFib this was \(O(1)\) as we only needed to keep track of the last two Fibonacci numbers. In case of shortestPathDownRight we need to create a grid of size \(n \times n\), so \(O(n^2)\). The notion of space complexity is very similar to time complexity, so we will not discuss it in depth.


  • Cutting Rods We are given a rod of integer length \(n\) and a list of length prices \(n\). The \(i\)th entry in the list corresponds to the profit we can get from selling the rod of length \(i\). How should we cut the rod so we maximise our profit? The key to our dynamic algorithm will be the observation that:

We cut the rod at position \(k\). Now we have a rod of lenght \(k\) and \(n-k\). Let us assume we know the maximum price for these two rods. Now we need to consider all the \(0 \leq k \leq \lfloor \frac{n}{2} \rfloor + 1\) (the problem is symmetric so computing for \(\frac{n}{2} \leq k\) would be redundant. For \(k=0\) we just take prices[n]. The cutting introduces subproblems which are smaller than the initial problem and they are overlapping! Let us put this into code:

# For comparing the running times
import time
# For testing
from random import randint

def dynamicCutRod(n,prices):
    # setting the initial values of variables
    assert n >= 0 and n == len(prices)
    # trival cases
    if n == 0:
        return 0
    if n == 1:
        return prices[0]
    
    # setting up needed variables
    table = {}
    currLen = 2
    table[0] = 0
    table[1] = prices[0]
    while currLen < n + 1:
        # no cuts for a given len
        table[currLen] = prices[currLen - 1]
        # considering all possible cuts for a give len
        for k in range(1,currLen//2 + 1):
            # take the maximal one
            if table[currLen] < table[k] + table[currLen - k]:
                table[currLen] = table[k] + table[currLen - k]     
        currLen += 1
    return table[n]
        
# for testing purposes
def bruteForceRecursive(n,prices):
    assert n >=0
    if n == 0:
        return 0
    if n == 1:
        return prices[0]
    currLen = n
    res = prices[n-1]
    for k in range(1,n//2 + 1):
        res = max(res, bruteForceRecursive(k,prices) + bruteForceRecursive(n-k,prices))
    return res

# testing
for i in range(1, 11):
    prices = []
    for j in range(i):
        prices.append(randint(1,10))
        
    assert bruteForceRecursive(len(prices),prices) == dynamicCutRod(len(prices),prices)
    
# comparing times
prices = []
for i in range(20):
    prices.append(randint(1,10))
    
start = time.time()
print(bruteForceRecursive(len(prices),prices))
end = time.time()
print("Time for brute:" + str(end - start))

start = time.time()
print(dynamicCutRod(len(prices),prices))
end = time.time()
print("Time for dynamic:" + str(end - start))
66
Time for brute:1.457252025604248
66
Time for dynamic:0.0029768943786621094

Time complexity? For each \(0\leq i \leq n \) we need to consider \(i\) different cuts. This is the sum of arithmetic series so \(O(n^2)\). We memoize only the optimal solutions to subproblems, therefore space complexity is \(O(n)\).

Characteristic features of dynamic problems#

All problems which can be tackled with the use of Dynamic Programming (DP) have two main features:

  1. Optimal substructure: In broad terms, that solution to the problem can be formulated in terms of independent subproblems. Then you choose a solution/combination of optimal solutions to subproblems and show that this choice leads to an optimal global solution. For example, for the shortestPath problem we choose between the optimal solution to the tile above and tile to the left. For the rod problem, we choose between all possible \(n\) cuts of a rod and assume we have solutions to the shorter rods.

  2. Overlapping subproblems: The subproblems which we split the main question into should repeat. Eliminating the need to recompute the subproblems (by memoising them) should speed up our algorithm. For example, dynamicFib used two variables to keep the results of computing previous Fibonacci numbers.

Common approaches to DP#

There are two main schools of thought when it comes to solving DP algorithms:

  1. Memoization is using the memory-time trade-off. It remembers the results to the subproblems in a dictionary memo and recalls them when needed. If we have the result in memory, we take if from there, otherwise compute it.

  2. Bottom-up approach starts with the trivial cases of the problem and builds on them. I relies on the the fact that subproblems can be sorted. So we first compute the optimal cutting for a rod of length 1 and then length 2 and so on…

Both usually lead to the same time complexities.

Advanced Examples#

  • 0-1 Knapsack The problem is about a backpack (knapsack) of an integer volume \(S\), we are given lists spaces and vals which correspond to the size and value of the objects we might want to pack. The trick is to pack the objects of the highest accumulate value which fit into the backpack. We will consider prefixes of the sizes list in order of length and put the intermediate results in a table. Compare the bottom-up and memoized approaches:

# For comparing the running times
import time
# For testing
from random import randint

# bottom up approach
def knapSack(wt, val, W, n): 
    K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 

# memoized
memo = {}
def knapSackMemo(wt,val, W, n):
    # base case
    if n == 0 or W == 0:
        memo[(n,W)] = 0
        return 0
    # check if memoized
    if (n,W) in memo:
        return memo[(n,W)]
    # if not, calcuate
    else:
        if wt[n-1] <= W:
            memo[(n,W)] = max(knapSackMemo(wt,val,W-wt[n-1],n-1)+val[n-1],
                              knapSackMemo(wt,val,W,n-1))
            return memo[(n,W)]
        else:
            memo[(n,W)] = knapSackMemo(wt,val,W,n-1)
            return memo[(n,W)]
        
# brute force for testing
def bruteForce(wt, val, W):
    res = 0
    # all combinations of the elements
    for i in range(2**len(wt)):
        sumSize = 0
        sumVal = 0
        for j in range(len(wt)):
            if (i >> j) & 1:
                sumSize += wt[j]
                sumVal += val[j]
            if sumSize > W:
                sumVal = 0
                break    
        res = max(sumVal, res)
    return res

# testing
for _ in range(10):
    sizes = []
    vals = []
    S = randint(0,200)
    memo = {}
    for _ in range(13):
        sizes.append(randint(1,10))
        vals.append(randint(1,20))
    
    br = bruteForce(sizes,vals, S)
    btup  = knapSack(sizes,vals,S,len(sizes))
    mem = knapSackMemo(sizes,vals,S,len(sizes))
    
    assert btup == br and mem == br
    
start = time.time()
print(bruteForce(sizes,vals, S))
end = time.time()
print("Time for brute:" + str(end - start))

start = time.time()
print(knapSack(sizes,vals,S,len(sizes)))
end = time.time()
print("Time for bottom-up:" + str(end - start))

memo = {}
start = time.time()
print(knapSackMemo(sizes,vals,S,len(sizes)))
end = time.time()
print("Time for memoized:" + str(end - start))
135
Time for brute:0.019960880279541016
135
Time for bottom-up:0.00098419189453125
135
Time for memoized:0.0009658336639404297

In this case, the memoized approach is the fastest as it does not usually require to consider all (n,W) pairs. However, both bottom-up and memoized approach have space (and time) complexity of \(O(nS)\). The brute force has time complexity of \(O(2^n)\), where \(n\) is the length of the sizes list.


  • Scheduling With all the chaos that COVID caused universities are going fully remote. The head of your department asked the lecturers to send the timeslots in which they can do lectures. This is a list timeslots which consist of pairs of integers - the start and end of the timeslot. If timeslots overlap, then we choose only one of them. Lectures can start at the same time the previous lecture finished. You aim to pick the subset of timeslots which assures that the sum of teaching hours is maximum. Return the maximum number of hours.

The question is similar to the previous one. We are given a list of items (timeslots) and need to come up with an optimisation. The value of each subset is the sum of hours of its elements. To speed things up in later stages, we will sort the timeslots by the ending time. This is done in \(O(nlog(n))\). We will then consider the prefixes of the sorted array and memoize optimal results. memo[n] will store the maximum number of hours from the prefix of n length.

# For comparing the running times
import time
# For testing
from random import randint

# utility function to speed up the search
def binarySearch(timeslots,s,low,high):
    if low >= high:
        return low
    mid  = (low + high) //2
    if timeslots[mid][1] <= s:
        return binarySearch(timeslots, s, mid+1, high)
    else:
         return binarySearch(timeslots, s, low, mid)

# init memo
memo = {}
# assumes that timeslots array is sorted by ending time
def schedule(timeslots, n):
    # base case
    if n == 0:
        memo[0] = 0
        return 0
    # memoized case
    elif n in memo:
        return memo[n]
    # else calculate
    else:
        s,e = timeslots[n-1]
        # in log time
        ind = min(binarySearch(timeslots,s,0,len(timeslots)),n-1)
        memo[n] = max(schedule(timeslots,n-1), schedule(timeslots,ind) + (e - s))
        return memo[n]
    
# brute force for testing
def bruteForce(timeslots):
    res = 0
    # all combinations of the elements
    for i in range(2**len(timeslots)):
        sumHours = 0
        already_chosen = []
        for j in range(len(timeslots)):
            if (i >> j) & 1:
                s, e = timeslots[j]
                sumHours += e - s
                already_chosen.append(timeslots[j])
            # checking if a valid combination of timeslots                 
            for k in range(len(already_chosen)-1):
                if not (s >= already_chosen[k][1] or e <= already_chosen[k][0]):
                    sumHours = 0
                    break                 
        res = max(sumHours, res)
    return res    
    
# testing
for _ in range(10):
    memo = {}
    timeslots = []    
    for _ in range(12):
        s = randint(0,100)
        e = randint(s,100)
        timeslots.append((s,e))
    timeslots.sort(key = lambda slot: (slot[1],slot[0]))
    
    br = bruteForce(timeslots)
    mem = schedule(timeslots,len(timeslots))  
    assert br == mem
    
start = time.time()
print(bruteForce(timeslots))
end = time.time()
print("Time for brute:" + str(end - start))

memo = {}
start = time.time()
print(schedule(timeslots,len(timeslots)))
end = time.time()
print("Time for memo:" + str(end - start))
82
Time for brute:0.14516472816467285
82
Time for memo:0.0010349750518798828

Time complexity of this solution is \(O(nlog(n))\). Why?

Exercises#

  • Tiling problem You are given a \(2 \times n\) board and \(2 \times 1\) tiles. Count the number of ways the tiles can be arranged (horizontally and vertically) on the board.

HINT: You have seen this algorithm before.


  • Maximum sum subarray You are given an array with \(1\) and \(-1\) elements only. Find the array of the maximum sum in \(O(n)\). Return this maximal sum. E.g. [-1,1,1,-1,1,1,1,-1] -> 4.

HINT: Consider the sums of prefixes of the array.


  • Longest snake sequence You are given a grid of natural numbers. A snake is a sequence of numbers which goes down or to the right. The adjacent numbers in a snake differ by a maximum 1. Define a dynamic function which will return the length of the longest snake. E.g.

9, 6, 5, 2

8, 7, 6, 5

7, 3, 1, 6

1, 1, 1, 7

-> 7

References#

  • Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms”, Third Edition, MIT Press, 2009

  • Prof. Erik Demaine, Prof. Srini Devadas, MIT OCW 6.006 “Introduction to Algorithms”, Fall 2011

  • GeeksforGeeks, Find maximum length Snake sequence

  • Polish Informatics Olimpiad, “Advetures of Bajtazar, 25 Years of Informatics Olympiad”, PWN 2018