The best way to overcome your fear is to face it.
I know a lot of good coders who used to fear DP, but now they have conquered the topic. The good quality of DP is the more you love it, the same love you’ll get back in return. On this positive note let’s start with this part-2 of our DP series.
Today we will solve the most basic and the most interesting DP problem from AtCoder Educational DP Contest ( Frog 1 ).
You can read the problem statement from here. But let me give you a brief overview of the problem statement. It says — We are given N stones, each with a height hi, and the cost of jumping from stone-i to stone-j is |hi — hj |. Currently, we are at stone-1, we can make jumps of sizes 1 or 2 such that finally, we reach the N’th stone. Our task is to minimise the total cost of all the jumps.
We are going to follow the same sequence of steps which we performed in Part-1 blog. In case you missed it here it is!
Let's start solving
STEP 1 — Build a naive recursive solution
Just do whatever the problem statement stated. If we are currently at index i check whether index i+1 or i+2 gives the minimum cost, and from there we recurse forward either to index i+1 or i+2 respectively.
There are two important base-cases involved in this problem.
- We are currently at the N’th stone. We can’t move forward so return 0.
- We moved ahead from the N’th stone. ( This case is possible because at each step we would check which of either jump size i.e. either 1 or 2 would give us the minimum cost so from the (N-1)’th stone too we will check for a jump of size 1 and of the size of 2). We are at an invalid stone since we need the minimum total value in order to discard a jump till this stone we have to assign a very huge cost to this jump. So we return INT_MAX( for the mean-time consider it as infinity ).
Let’s look at the recursive code
The code is simply whatever we discussed above.
Time Complexity — O(2^n) ( as in every step we have 2 choices to jump either over 1 stone or 2 stones. Thus by basic P&C we can very easily show that the total number of ways will be 2^n )
STEP 2 — Memoize the recursive solution
Now look at the above code and try to find out which parameter is changing at each step. It’s none other than curr_idx ( denoting the current index at each moment ). So, we have just 1 parameter to memoize, indicating we have to build a 1-D array to store all memoized values. Just like what we did in the memoized code of the previous blog, we will follow the same procedure here too; i.e. memoize the value returned from each function call.
Here is the memoized code
Yes! we are done.
Time Complexity — O( N ).
To check your understandings you can read the problem from the above link and try submitting your code here.
You can also try a similar problem from LeetCode too.
Bonus Task
To challenge your understanding you can try a slight difficult version of this problem from here.
Hint: In the current problem we solved for jumps of sizes 1 and 2 only. Scratch your brains and try to think about how we would have proceeded if we were allowed to make jumps of sizes 1,2,3….M.
For any doubts in the above explanations, you can mail me at - ankitpandeycu@gmail.com
Share this blog with your peers if you find it useful.
Hope it helps.
AnkitCode99 here….
