What is Dynamic Programming?

Introduction #

If you are learning Dynamic Programming for the first time it seems esoteric and intimidating. I may provide some comfort knowing that that was the intention of the name. Confused? See below a quote from the founder:

“The 1950s were not good years for mathematical research… I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics… What title, what name, could I choose?… It’s impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities. - Richard Bellman

So Dynamic Programming… is just a name, a marketing decision essentially. So hopefully that will make it seem more approachable, but we still need to answer, what is Dynamic Programming?

Definition #

In the simplest terms Dynamic Programming, or often called by its unfortunate acronym DP, is the process of taking a complex problem, breaking it down into simpler reusable subproblems.

For DP to be applicable the problem being solved often have the following characteristics:

1. Can be broken down into overlapping subproblems or smaller version of the original problem that are re-used multiple times.
2. The problem has an optimal substructure, an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem.

Example - Fibonacci Sequence #

The classic Dynamic Programming example is the Fibonacci sequence. You start with the numbers 0 and 1 then each subsequent number is the sum of the previous two. So the first five numbers would be 0, 1, 1, 2, 3.

Now, if we are tasked to solve a problem that asks us what the n^th Fibonacci number we can break into a smaller subproblems. $F(n)$ as we know is equal to the sum of the two previous Fibonacci numbers in the pattern, $F(n - 1)$ and $F(n - 2)$. So if we add them together we solve the original question, $F(n) = F(n - 1) + F(n - 2)$.

This is considered optimal substructure as the original problem can be formed from the solutions for the overlapping subproblems. The subproblems are overlapping as it as the numbers rise you need the previous solutions. $F(4)$ is needed to solve for $F(5)$.

Complexity #

Now why is this efficient? Well since our new approach can reuse the results of subproblems our solution will be near $O(n)$. This is comparison to the brute force solution of $O(2^n)$.

Similar Algorithms #

Some different algorithm techniques share qualities with DP by are not apples to apples. For example, Greedy Algorithms have optimal substructure, but no overlapping subproblems. And divide and conquer algorithms use subproblems, but they do not overlap.

Recap #

Dynamic programming is useful because it can

• break a complex problem into manageable subproblems
• avoid redundant work of overlapping subproblems
• use the subproblems to solve the initial complex problem.
• improve complexity in comparison to brute force solutions.

Implementation #

The two ways to implement DP algorithms are:

1. Bottom-up or tabulation
2. Top-down or memoization

Bottom-up (Tabulation) #

Tabulation is implemented with iteration starting with the base cases. Continuing with the Fibonacci sequence, our base cases are $F(0) = 0$ and $F(1) = 1$. If we wanted to find $F(5)$, we would start with our base cases and move up to $F(2)$ first, then $F(3)$, $F(4)$, finally $F(5)$.

Top-down (Memoization) #

This time we use recursion, i.e. a function calling itself, and make it efficient with memoization (making a “memo” or caching results). Now to find the 5^th fib number we start with passing in the 5 and call from the addition of the two overlapping subproblems.

Which Is Better? #

• A bottom-up implementation’s runtime is usually faster, as iteration does not have the overhead that recursion does.
• A top-down implementation is usually much easier to write. This is because with recursion, the ordering of subproblems does not matter, whereas with tabulation, we need to go through a logical ordering of solving subproblems.

When to use DP #

1. The problem can be broken down into “overlapping subproblems” - smaller versions of the original problem that are re-used multiple times
2. The problem has an “optimal substructure” - an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem

1) Optimum Value #

• optimum value = min/max/longest/shortest of something
• number of ways to do something or if it’s possible to reach a certain point.

either greedy or DP

2) Future “decisions” depend on earlier decisions #

• We need to factor in results from previous decision. This is why greedy algos won’t work.

NOTE:

• If deciding if this is applicable assume the negative
• Then link of why greedy wouldn’t work.

A common characteristic of problems that can be solved with dynamic programming is that they ask for the maximum or minimum of something.

Strictly speaking, both can be parallelized, however the steps required to parallelize dynamic programming approaches are quite complex. So generally speaking, divide and conquer approaches can be parallelized while dynamic programming approaches cannot be (easily) parallelized. This is because the subproblems in divide and conquer approaches are independent of one another (they do not overlap) while in dynamic programming, the subproblems do overlap.

to convert a top-down solution into a bottom-up solution, we must first find a logical order in which to iterate over the states.

Framework #

For this section we will use the below problem.

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

In Dynamic Programming we will need to define a state. A state is a set of variables that can be sufficiently describe a scenario. These variables are shockingly called, state variables.

In our example we have one state variable the current step we are on. If we use var s to represent the current step and every unique value of s is unique. Example s == 6 means we are on the 6th step.

THE FRAMEWORK #

1. Determine function to compute and Data Structure to contain the answer, for every given state.

• Top-down / Memoization = recursive function and hashmap.
• bottom-up / tabulation = nested loop and array

2. Find the overlapping sub problems recurrence relation = equation that relates different sates with each other.

With our problem, if we need to find how many possibilities there are to reach the 30th step. Based on our constraints of taking only one or two steps per a turn we must of came from the 28th or the 29th step. Thus, the answer is equal to the number of ways we can climb to the 28th stair plus the number of ways we can climb to the 29th.

Described in a equation as $dp(i) = dp(i - 1) + dp(i - 2)$.

3. Base cases To avoid infinite calls we need a base case that stops the function and allows it to eventually return an actual number.

Ask, “What state can I find the answer without using Dynamic Programming?”

For this problem it would be if we wanted to find the answer for the first or second step.

• dp(1) = 1
• dp(2) = 2