“Programming isn’t about what you know; it’s about what you can figure out.” — Chris Pine
Hola amigos! Hope you all enjoyed and learnt something useful from the previous blog where we discussed the ‘take it or leave it’ method along with the consideration of where to begin from. Today, we will learn the most loved DP problems solving technique, and trust me after going through the blog you would be able to solve plenty of amazing DP problems. Its show time…..
Let’s start with the discussion
Today, we will again solve a competitive coding problem form CodeForces named — “ Vacations ”. It is based on a new principle which says “to whatever the problem says”.
As the name of the principle indicates we have to simply carry-out the tasks in the order asked in the problem.
The problem statement is as follows — You are on a vacation of n, so you decided to hone your coding skills by participating in coding contest or maintaining your fitness by going to gym. For the i-th day there are four options:
- a[i] equals 0, if on the i-th day of vacations the gym is closed and the contest is not carried out;
- a[i] equals 1, if on the i-th day of vacations the gym is closed, but the contest is carried out;
- a[i] equals 2, if on the i-th day of vacations the gym is open and the contest is not carried out;
- a[i] equals 3, if on the i-th day of vacations the gym is open and the contest is carried out.
On each of days you can either have a rest or participate in contest (if it is carried out on this day), or do workout (if the gym is open on this day).
You have to calculate minimum number of days you will rest, keeping in mind you cannot perform same activity on consecutive days.”
Constraint : ( 1 ≤ n ≤ 100 and 0 ≤ a[i] ≤ 3 )
For further clarifications, you can read the problem statement from here.
Let’s start solving
STEP 1 — Build a naive recursive solution
The best part about to whatever the problem says is you can very easily build recursive solutions. Here is goes for all possible cases when starting from day 0;
- Base Case : We reached the n’th day (last day of our vacation). We have nothing to consider further so return 0.
- task[ current_day ] = 0 : We have no options other than taking rest, so we increase the rest count by 1.
- task[ current_day ] = 1 : Here we check that if we have done task-1 the previous day we have no options but to take rest and we simply increase rest count by 1. On the contrary, we have 2 options : Either participate in coding contest today, or take rest. So we try both the possibilities and return the value which gives minimum number of total rests.
- task[ current_day ] = 2 : Same as above by changing the values 1 by 2 in our recursive calls.
- task[ current_day ] = 3 : Here we simply check if previous day we did task-1 we recurse on task 0 and task 2 respectively and return the minimum out of those two values. If we did task-2 the previous day we recurse on task 0 and task 1 and then return the minimum value. If we took rest a day before we then check for all possible activities we can do today. ( Try to think in real world scenario if you didn’t get this )
Let’s look at the recursive code made from the above discussions
Time Complexity — Exponential ( at every index we have multiple options to select from, one of the worst case can be alternative 0s and 1s, which would make the time complexity O( 2⁵⁰ )).
STEP 2 — Memoize the recursive solution
From the above recursive code, it is very clear that the changing parameters are none other than, curr_day and previous_day_task. Our task is now just reduced to memoize the value returned for each possible value of current-day and previous_day_task.
In order to memoize the returned value we can build a DP matrix of size 105*3 because we have at-max 100 days and we smartly reduced from 4 possible tasks to 3 in the above recursive code using the last else-statement.
So here is the memoized code.
Time Complexity — O( 100*3 ).
This way you once again solved a DP problem rated 1400 on CodeForces. Kudos!
So, you learnt a new DP problems solving technique. Let me tell you, the method we discussed today is the base of many past interviews as well as contest problems. So, now I believe you would be able to conquer them.
To check your understanding try submitting your code here.
Try out these 2 problems to get solid grasp over the concept we learnt.
- AtCoder Educational DP-Contest — Problem C ( Difficulty — Easy )
- Google Kickstart 2020 Round D — Problem B ( Difficulty — Medium )
Hope you enjoyed the blog and learnt something new.
For any doubts in the above explanation or regarding solutions of the mentioned practice problems you can mail me at — ankitpandeycu@gmail.com
Share this blog with your peers if you find it useful.
Hope it helps.
AnkitCode99 here….
