Dynamic Programming

Dynamic programming is a method of reducing a complicated problem into simpler sub-problems in a recursive manner.

This tends to be modeled as a tree.

For a problem to be solvable with dynamic programming, there must be

• optimal substructure
• overlapping sub problems

Optimal substructure

An optimal solution can be obtained by combination of optimal solutions to the subproblems.

Fibonacci sequences are normally used to showcase this. $F_{i} = F_{i-1} + F_{i-2}$

Overlapping subproblems

There is a very clear recursive relationship, and the overlapping subproblems are the repeat computes of $F(2)$.

$F(4)$ depends on $F(3)$ and $F(2)$.

$F(3)$ depends on $F(2)$ and $F(1)$.

$F(2)$ depends on $F(1)$.

This is considered a top-down approach. We started at the larger problem and defined the relationship with the subproblems. If we implemented this recursively like so

1def fib(i):
2  if i <= 1:
3    return i
4  return fib(i-1) + fib(i-2)

We'd spend time repeatedly solving those subproblems. A solution to this is memoisation, where we memorise the solution and therefore only have to calculate it once

1def fib(i, memo={}):
2  if i in memo:
3    return memo[i]
4  if i <= 1:
5    memo[i] = i
6    return memo[i]
7  memo[i] = fib(i-1) + fib(i-2)
8  return memo[i]

This should be tidied up, but hopefully it conveys the point. Now when we visit a subproblem, we check if we've seen it before and return the result, otherwise we calculate the result, store it, and then return it.

Another approach is bottom-up. We determine what the smallest problem is, and build our way back to the solution. Normally this is done using a table of some sort

The identified relationship is the same, but how we implement it is different. We know $F(0) = 0$ and $F(1) = 1$ and we can proceed with calculating the rest.

1def fib(i):
2  dp = [0] * (i+1)
3  dp[0] = 0
4  dp[1] = 1
5
6  for n in range(2,i+1):
7    dp[n] = dp[n-1] + dp[n-2]
8  return dp[i]

In both the top down and bottom up solution, we identified some "starting" data. 0 and 1 are our two starting points. From there we can calculate the rest of the problem.

Technically speaking our relationship only ever depends on the last two states, so we could also write it as.

1def fib(i):
2  dp_0 = 0
3  dp_1 = 1
4
5  for n in range(1,i):
6    dp_0,dp_1 = dp_1, dp_0+dp_1
7  return dp_1

This is one of the advantages of approaching the problem in a tabular form, there is the potential to disocver solutions that use constant memory.

Templates

Top Down

memo = empty map
f(subproblem):
  if subproblem in base case:
    return result
  if subproblem in memo:
    return cached result
  memo[subproblem] = recurrence relation formula
return f(initial subproblem)

Bottom Up

dp = []
seed base case to dp
for i in range(basecase+1):
  dp[i] = recurrence relation formula

return dp[-1]