Dynamic Programming for Dummies.

So as a young Leetcode Enthusiast dynamic programming has always been an unsolved mystery for me. I remember back in November when I was trying to solve a dp question I was puzzled by the sheer complexity of it.

source spiderman no way home

However, there are two parts when it comes to understanding dp let’s go over to the easy part first.

Solving Dynamic Programming with HashMap (a.k.a Top-down approach)

These are the easiest form of dp questions where you are using a recursive approach to solve a problem and optimizing a problem with a HashMap. Perhaps, the easiest question to show how the top-down approach works is a Fibonacci Number series. (Leetcode problem no 509). So here’s our question.

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n)

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Here we are using the recursive approach to derive the Fibonacci of a number however we can see that there are repetitive problems. For example, if you are trying to get fib(4) you need to compute fib(4 –1) = fib(3) and fib(4-2) = fib(2); to get fib(3) we need to compute fib(3–2) = fib(1) and fib(3–1) which is fib(2) so here we can see that fib(2) is a repeating subproblem which is where our dp comes in the picture.

A dynamic programming is nothing but a way to optimise our computation here we can see that we can store our result in a map like structure which we can refer to in the future if similar type of sub-problem is encountered.

So with the top-down dp our solution would look similar to something like this.

Here we can see that we are storing the subproblem and referring to it when a similar subproblem is encountered. With this optimization, we can see our runtime has gone down significantly from 18ms to 0ms on leetcode. Now let’s solve this same problem with the bottom-up approach.

Solving Dynamic Programming with Array (a.k.a bottom-up approach)

The toughest part about this approach is we tend to focus on optimization rather than identifying the base condition. So the next question that will arise in your mind is how come we don’t face the same problem in a recursive approach and the answer to this question is quite simple when we deal with recursion the first thing that comes to our mind is the base condition without which our recursion will fall flat on its face.

Another, thing with this approach is when we work on the bottom-up solutions we deal with iteration rather than recursion, and thinking about the base condition is not something, which is a common practice when it comes to iteration and this is why our bottom-up dp’s fail most of the time. I will try to explain this with a sample solution.

Here instead of storing the pre-computed solution in a map, we are building the array from bottom-up till the value n. We are starting our loop from 2 and as we have discussed earlier in order to compute the fib(2) we will need fib(1) and fib(0) before starting our iteration we are defining their value inside our array. Once get fib(2) we can compute fib(3) so on and so forth. Thus here our solution is getting build-up step by step unless we reach the final goal.

A Fibonacci number is a very easy dynamic programming question let’s crank up the difficulty.

Leetcode 45. Jump Game II:

Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Not all the dp questions can be solved with a top-down approach that’s why it is important to learn the bottom-up approach. The basic idea for solving this question is we have to built up the solution at every step until we reach the final destination. So for the first input we know that in order to reach index 0 we will need 0 steps and subsequently, it will take 1 step to reach from index 0 to 2 so on and so forth so.

Here we know that for every sample set it would take 0 no of steps to get to index 0 that’s why we are definingdp[0] = 0

Now the next step here is to check how many indexes can we cover from 0 using the array which has been given to us also we have to be cautious that we don’t exceed the index and cause an index out of bounds exception.

And the final piece of the puzzle is updating our table. Here we need to update the step count when we encounter a step that is smaller than the one which we have stored in our table. So initially, we would have a value 2147483647 stored inside at every index, and when we compute a step at a particular position we check whether it is smaller than the one which he has stored. if so update the table. This comes in handy when we can reach the last index with some minimal steps. We perform this computation for n no of steps. And voila we have our solution.

That’s it folks for today. I hope this post helped you in your journey. Comment your thoughts or your question so I can answer them. And if you want me to cover some more dynamic programming strategy hit the clap button and share some love.