# 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
else:
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)
/        \
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