# The No bullsh*t guide to dynamic programming

When digging in to AI topics like reinforcement learning, the topic of dynamic programming keeps popping up. Examining formal definitions of dynamic programming yields a whole bunch of overly complex bullshit. The reality is, the concept is really simple.

Dynamic programming is all about avoiding repetitively solving the same problem every single time you run the program. This doesn’t matter much with trivial computations, but when you are dealing with algorithms that have exponential time complexities or worse, you can save a lot of time going this route.

Dynamic programming is a natural fit for recursive algorithms. It doesn’t usually fundamentally alter the algorithm itself, and helps you improve the performance considerably in non-trivial situations.

# A little bit of bullshit

OK, I lied. To understand dynamic programming we do need to slog through a little crap. If dynamic programming is to be used, two conditions need to be met. The problem must have:

- Optimal substructure
- Overlapping sub-problems

If the problems are non-overlapping, we use “divide and conquer” instead. This is why sorting is not done with dynamic programming.

**Optimal Substructure**

This is the bullshit way of basically saying “recursive.” Basically, in a problem with optimal substructure, we can solve the problem by combining the optimal solutions to the problem’s sub-problems. Usually this is a recursive situation. Basically if a problem’s sub-problems are just simpler versions of themselves, it exhibits this optimal substructure.

**Overlapping sub-problems**

All the sub-problems need to be similar. Your algorithm should be solving the same sub problems over and over again. Factorial, for example. When you compute 5!, you need to compute 4!, 3!,2! and 1!. When you compute 4! you need to compute 3!, 2! and 1!. You get the picture.

**Re-Memo-it**

OK, that subtitle is lame. Shoot me, I’m a nerd. Dynamic programming for some problems comes down to one simple rule! Remember that intermediate bullshit! In computer science terms we call this memoization.

Memoization is about as straightforward a concept as you can get. Whenever you solve a sub-problem, stick the solution in a table, and next time, don’t solve it again! Pretty darn straight forward. Memoization is typically considered a top-down approach in that it solves smaller and smaller problems. You can also go the other way and solve bigger and bigger versions.

We are going to code up a simple example in C#. We will use our favorite Fibonacci function. Here is our base version. Note that I am deliberately using long integers because factorials get big, fast.

`public static long Fibonacci(long n)`

{

if (n <= 1)

{

return n;

}

return Fibonacci(n-1)+Fibonacci(n - 2);

}

I’m going to add a little time keeping code here so we can measure performance. I am going to wrap the CALL to factorial, not the method itself, because we only want the final result:

public static void TimedFibonacci(long n)

{

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

long result = Fibonacci(n);

stopwatch.Stop();

TimeSpan ts = stopwatch.Elapsed;

Console.WriteLine($"Fibonacci of {n}: {result}");

Console.WriteLine($"RunTime: {ts.Hours:00}:{ts.Minutes:00}:

{ts.Seconds:00}.{ts.Milliseconds/10:00}");}

So given this timing code, we can run it and on my computer (a fairly robust machine), Fibonacci(40) takes about 3.25 seconds and Fibonacci(45) takes about 35.5 seconds.

Obviously from here its going to just get worse. So to improve this, we call upon our new hero dynamic programming.

We are going to add a dictionary with a long index (just in case) and a long value.

`private static Dictionary<long, long> _memos = `

new Dictionary<long, long> {{0, 0}, {1, 1}};

We’ve even added our two base cases to the memos so we don’t need to compute them. Note the dictionary is static because we want it to persist across calls. Our algorithm simply becomes this:

`public long MemoFib(long n)`

{

if (!_memos.ContainsKey(n))

{

_memos[n] = MemoFib(n-1)+MemoFib(n-2);

}

return _memos[n];

}

Refactor TimedFibonacci and replace the Fibonacci call with MemoFib.

Now, when I run it, I get the same computed results, but literally less than a tenth of a second, even for Fib(45). Fib(75) and Fib(92) are almost instant as well. I couldn’t go higher than 92 without longs overflowing.

So there you have it. Basic dynamic programming is conceptually pretty easy and can DRASTICALLY, INSANELY improve performance of your algorithms if they meet the appropriate conditions. That’s not bullshit!

Have fun with this. There are lots of recursive problems it can apply to.