Day 21 | Dynamic Programming - 1| Covered Path | C++

Hello!

Today we finish 3rd week of our consistency, and there let's reward ourselves by stepping into one of the most important algorithmic paradigms in competitive programming which is Dynamic Programming.

Today we are solving the Covered Path, this problem can be solved without Dynamic Programming and only using mathematics. But you should try that on your own, here we will try to learn a little bit about dynamic programming.

So the problem says that we start a segment at speed v1 and end the segment at speed v2 and in any second the maximum change of speed was d. We have to calculate the maximum possible distance traveled given that the configuration is also possible.

When I read the last line, I stopped thinking about cases when it is never possible as it is not of my concern in this problem.

So basically, let's start with some rough sketching. Let's just create a method by which we pass the speed and time and it tells what is the maximum distance it can travel.

Something like this

int calculate_distance(int speed, int time){}

Now how do we actually calculate 🤔

If I am traveling at speed s for the next 1 second, then the maximum distance will be

s + maximum distance I can travel in the remaining (time - 1) seconds

So I actually converted it to a smaller logical problem.

int calculate_distance(int speed, int time){
    int max_possible = 0;
    for(int delta = -d; delta <= d; delta++){
        int next_speed = speed + delta;
        if(next_speed <= 0)continue;
        max_possible = max(max_possible, 
                            calculate_distance(next_speed, time-1) + current_speed);
    }
    return max_possible;
}

But remember that at T = 1 (during exit), our speed should be v1, thus impossible to have speed!=v2 and T = 1

int calculateDistance(int current_speed, int time_remaining){
    if(time_remaining == 1 && current_speed != v2) return 0; // If in the end, speed should be v2
    if(time_remaining == 0)return 0;
    int max_possible = 0;
    for(int delta = -d; delta <= d; delta++){
        int next_speed = current_speed + delta;
        if(next_speed <= 0)continue;
        max_possible = max(max_possible, 
                            calculateDistance(next_speed, time_remaining - 1) + current_speed);
    }
    return max_possible;
}

I tried submitting this solution and this is the result - TIME LIMIT EXCEEDED

Because the time complexity of this solution is huge. Tell me in retweets or LinkedIn comments what is the time complexity of this implementation - the first homework for you

Let me tell you something that is happening here

Let's say I call the method starting at 10,10

f(10,10) for d = 3

this calls further

f(13,9), f(12,9), f(11,9), f(10,9), f(9,9), f(8,9), f(7,9)

Now these will further call many functions

But notice that f(13,9) will also call f(14,8) so do f(12,9) and f(11,9)

So this method will be recalculated at least 3 times. This has happened way too many times.

What if we store the data we calculated so we won't have to re-calculate is again?

We do something like this

int calculateDistance(int current_speed, int time_remaining){
    if(time_remaining == 1 && current_speed != v2) return INT_MIN/2; // If in the end, speed should be v2
    if(time_remaining == 0)return 0;
    if(dp[current_speed][time_remaining] != -1)
        return dp[current_speed][time_remaining];
    int max_possible = INT_MIN;
    for(int delta = -d; delta <= d; delta++){
        int next_speed = current_speed + delta;
        if(next_speed <= 0)continue;
        max_possible = max(max_possible, 
                            calculateDistance(next_speed, time_remaining - 1) + current_speed);
    }
    dp[current_speed][time_remaining] = max_possible;
    return dp[current_speed][time_remaining];
}

This is called Memoization, I call it a type of dynamic programming, in fact generally the first one we learn and start using.

You can see my complete implementation here

You can read more about Memoization here