Dynamic programming

Dynamic programming is a technique for solving a problem that involves dividing the problem into subproblems, solving each subproblem once and storing the answer in case we see the same subproblem again.\newline

We can do Dynamic Programming top-down or bottom-up, which I explain with the example of calculating the \(n\)-th Fibonacci number.

Naive approach

Let \(F_i\) be the \(i\)th Fibonacci number, where \(F_1 = 1\), \(F_2 = 1\) and \(F_i = F_{i-1} + F_{i-2}\). Given some integer \(n >= 1\), what is an algorithm for calculating \(F_n\)? The naive approach is the following recursive algorithm:

def fib(n):
    if n <= 2:
        f = 1
        f = fib(n-1) + fib(n-2)
    return f

What is the running time for this algorithm? We write the recurrence relation:

\[T(n) = T(n-1) + T(n-2) + O(1)\]

\(T(n-1)\) includes the work of \(T(n-2)\), so:

\[T(n) >= 2 T(n-2)\]

We can subtract 2 from \(n\) for \(n / 2\) times before hitting 0 or 1 and each time we multiply by 2:

\[T(n) >= c 2^{n/2}\]

So the running time is exponential. However, if we draw the recursion tree:

	    /        \
	  fib(n-1)   fib(n-2)
	  /      \
	fib(n-2)  ...

We see that the same subproblems will appear multiple times.

Top-down Dynamic Programming

The top-down Dynamic Programming approach is sometimes called memoization. Recall that we store the answer to each subproblem after we solve it in case we see that subproblem again:

def _fib(n, memo):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    if n-1 not in memo:
        memo[n-1] = _fib(n-1, memo)
    if n-2 not in memo:
        memo[n-2] = _fib(n-2, memo)
    return memo[n-1] + memo[n-2]
def fib(n):
    memo = {}
    return _fib(n, memo)

There are \(n\) subproblems that we have to solve and each takes a constant amount of work, so the running time of this algorithm is \(O(n)\) instead of \(O(2^n)\).

Bottom-up Dynamic Programming

The bottom-up Dynamic programming is sometimes called tabulation. We perform the same calculations as the top-down approach, but instead of recursing down, we build the calculations starting from the bottom:

def fib(n):
    a = 1
    b = 1
    c = 1
    for _ in range(2, n):
        c = a + b
        a = b
        b = c
    return c