Take a look at the tasks here: Contest Link

A — Frog 1

The main thing to note in this problem is that the frog, from a position i can jump to only i + 1 or i + 2. This simplifies the problem.
We will create an array dp of size n (the total number of stones). dp[i] will store the minimum cost we can achieve till position i. An array jumps of size n will store the height of each stone.

For our base cases, we will set dp[0] = 0 and dp[1] = abs(jumps[1] — jumps[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Now, to get our final answer, dp[n-1], we need to solve all of our subproblems. To solve for any given position i, we need to have calculated the best we could do for positions i — 1 and i — 2. Why do we need to only consider positions i — 1 and i — 2? Well that is because the frog can only jump one or two stones ahead of its current position i.e to reach its current position i it had to have been at either i — 1 or i — 2.

We can simply do this in O(n).
For any given position i > 2, we can solve the subproblem this way:

dp[i] = min(dp[i-1] + abs(jumps[i] - jumps[i-1]), dp[i-2] + abs(jumps[i] - jumps[i-2]))

dp[i] will be the minimum cost to reach that position. To calculate this, we find the minimum cost of reaching positions i — 1 and i — 2. and then add the cost of jumping to position i and store the minimum.

Problem Link
Solution Link

B — Frog 2

This problem is slightly different from the first one. This time, we are given an additional variable k telling us the maximum size of a jump. k in the last problem was basically fixed to 2 as from a stone i we could only jump to i + 1 and i + 2.

Now, how do we modify our solution to handle this new case where k can be greater than 2?

We will still create an array dp (all values set to INFINITY) of size n (the number of stones we have). dp[i] will denote the minimum cost to reach stone i.
Our base case again, dp[0] = 0 (0 based indexing) as we start off from the first stone.

We use a nested loop:

for (int i = 0; i < n; i++) { // i represents the stone the frog is currently at.
        for (int j = i + 1; j <= i + k; j++) { // j represents a potential stone for the frog to jump to.
            if (j < n) // We have to check if the stone we want to jump to is not out of bounds.
                // Storing the total minimum cost to reach stone j from stone i.
                dp[j] = min(dp[j], dp[i] + abs(stones[j] - stones[i]));
        }
}

Here, the first for loop denotes that the frog is currently at stone[i]. The second for loop basically calculates the best we can do if we jump from stone[i] to stone[i+1], stone[i+2], stone[i+3] ... stone[i+k].
We are performing the min() operation because if the cost of jumping from i to j is higher than a cost we have already found, we do not want to update dp[j] to a higher cost.

We perform this for every position the frog could be at i.e it is performed for all positions i, i+1, i+2...n.

After performing these operations (solving all the subproblems), our final answer is stored at dp[n-1] (0 based indexing).

Problem Link
Solution Link

C — Vacation

We are given three types of activities. We get different amount of points by doing each activity each day. The only restriction is that we cannot do the same activity on two consecutive days.
For example, if we did activity A yesterday, we cannot do activity A today but we can do it tomorrow.

To solve this problem, we will maintain a 2D array, dp[n][3].

dp[i][0] will store the maximum points we can gain by doing activity A on day i.
dp[i][1] will store the maximum points we can gain by doing activity B on day i.
dp[i][2] will store the maximum points we can gain by doing activity C on day i.

Our base cases will be:

// If you swim in the sea in sea on the first day, you cannot get more than a[0] points.
dp[0][0] = a[0]; 
// If you catch bugs in the mountains on the first day, you cannot get more than b[0] points.
dp[0][1] = b[0]; 
// If you do homework at home on the first day, you cannot get more than c[0] points.
dp[0][2] = c[0]; 

For every day i, as we cannot do the activity we did on the previous day,

// If we do activity A today, we have to have done activities B or C on the previous day.
dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]); 

// If we do activity B today, we have to have done activities A or C on the previous day.
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]);

// If we do activity C today, we have to have done activities A or B on the previous day. 
dp[i][2] = c[i] + max(dp[i - 1][1], dp[i - 1][0]); 

Simply by checking for each day i, we can calculate the best we can do by the end of our last day.
As we can end by doing activities A, B, or C, our answer will be the maximum points gained on doing activities A, B, or C on the last day.
Time complexity: O(n)

Problem Link
Solution Link