Dynamic Programming

Dynamic programming a technique for solving recursive style problems. Put simply, dynamic programming is basically just using caches to improve recursive algorithms.

Let’s explain with an example: the Fibonacci sequence. Using a brute-force implemtation like so:

function fib(num) {
  if (num < 2) return num;
  else return fib(n - 2) + fib(n - 1);
}

However, this is not particularly efficient, with a computation time of $O(2^N)$. We can see that from this graph:

flowchart TB
    7["fib(7)"] --- 6["fib(6)"]
    7 --- 5["fib(5)"]

    6 --- 5a["fib(5)"]
    6 --- 4a["fib(4)"]

    5 --- 4["fib(4)"]
    5 --- 3["fib(3)"]

    3 --- 2["fib(2)"]
    3 --- 1["fib(1)"]

    2 --- 0["fib(0)"]
    2 --- 1a["fib(1)"]

    4 --- 3a["fib(3)"]
    4 --- 2b["fib(2)"]

    2b --- 0x["fib(0)"]
    2b --- 1x["fib(1)"]

    3a --- 2c["fib(2)"]
    3a --- 1c["fib(1)"]

    2c --- 0v["fib(0)"]
    2c --- 1v["fib(1)"]

    5a --- 4m["fib(4)"]
    5a --- 3m["fib(3)"]

    3m --- 2m["fib(2)"]
    3m --- 1m["fib(1)"]

    2m --- 0m["fib(0)"]
    2m --- 1am["fib(1)"]

    4m --- 3am["fib(3)"]
    4m --- 2bm["fib(2)"]

    2bm --- 0xm["fib(0)"]
    2bm --- 1xm["fib(1)"]

    3am --- 2cm["fib(2)"]
    3am --- 1cm["fib(1)"]

    2cm --- 0vm["fib(0)"]
    2cm --- 1vm["fib(1)"]
    
    4a --- 3at["fib(3)"]
    4a --- 2bt["fib(2)"]

    2bt --- 0xt["fib(0)"]
    2bt --- 1xt["fib(1)"]

    3at --- 2ct["fib(2)"]
    3at --- 1ct["fib(1)"]

    2ct --- 0vt["fib(0)"]
    2ct --- 1vt["fib(1)"]

That’s quite a bit of function calls. But, you’ll see that we call fib many times with the same arguments. Obviously, that would be much better if we could cache it.

Thinking in dynamic programming §

Let’s backtrack all the way to the start. We need to find the nth Fibonacci number. In dynamic programming, we break up the problem into pieces. So, in order to find the nth Fibonacci number, we add the n - 1th and the n - 2th. Now we have two pieces. Then three, etc… We’ll notice that there are many pieces that are repeated. We should cache this.

Another example is simple arithmetic. Say we have: $3+4+1+8+9+3+4+7+8+9+7$ Let’s rearrange this: $(3+4)+(3+4)+(8+9)+(8+9)+7+7+1$ Merge it furthermore: $2(3+4)+2(8+9)+7+7+1$ As you can see, we recognize that we have to evaluate some patterns multiple times. We can combine them to make a more efficient way.

Back to Fibonacci §

Now, how should we create our dynamic programming Fibonacci function? There’s two main ways, memoization and tabulation. If implemented properly (either way), the call stack should look like so¹:

flowchart TB
    7["fib(7)"]
    6["fib(6)"]
    5["fib(5)"]
    4["fib(4)"]
    3["fib(3)"]
    2["fib(2)"]
    1["fib(1)"]
    0["fib(0)"]

    7 --- 6
    7 --- 5
    6 --- 5
    6 --- 4
    5 --- 4
    5 --- 3
    4 --- 3
    4 --- 2
    3 --- 2
    3 --- 1
    2 --- 1
    2 --- 0

Much better. This only has a computation time of $O(N)$

Footnotes §

1. WHY do the lines from the left to the right look like that. Stupid. I can’t figure out how to make it not though. ↩