How to solve this problem using DP?

https://codeforces.com/problemset/problem/1389/B

We can probably have dp[n + 1][x + 1], and do operations on that.

dp[i][j] denotes reaching the ith position, using j left moves.

The recurrence is dp[i][j] = max(dp[i - 1][j], dp[i + 1][j - 1]) + a[i]

P.S: Take care of the base cases where j = 0, i = 0 etc

As you can find out, the answer will be max(dp[k][0], dp[k - 2][1]....) until j \le x and i > 1 .

If you can’t understand anything, don’t hesitate to revert back.

shudn’t the recurrence be dp[i][j]=max(dp[i-1][j-1],dp[i+1][j-1])+a[i]
bcz even if we go left it is considered as a move.

we can solve this using 2D dp and the dp state would be dp[N][z] , but there is one more thing mentioned in the problem , we can’t make more than one consecutive move to left, so we can use 3D dp to handle it and dp state would be dp[N][z][2].
And each time we will move two options- >
1 -> move right
2-> move left , if last move was a right move
and take max of all the options.

At first i forgot about the condition that we r not allowed to make two consecutive moves to the left, but it still got accepted :sweat_smile: , may be due to weak test cases.

But here is the correct approach :slightly_smiling_face:
Code: https://codeforces.com/contest/1389/submission/88413898

No that’s because there is no reason to move left more than once.

In fact you can prove the solution is of the form
RRRR ...RLRLRLRL... RRRR

1 Like

Ohh :sweat_smile:
I just tried to make a counter testcase , but couldn’t come up with one .
It seems like the soln is always of the form mentioned by u .Thanks for clearing it @everule1 :+1:

https://codeforces.com/contest/1389/submission/88375463

See you require unique states to solve any dp problem, now in this, we need to keep track of which position we are at, how many moves to the left we have made, how many total moves are left, and if our last move was one to the left. Now this would lead to a complexity of n^2 because we are keeping track of how many moves are remaining and the position we are at.

If you observe carefully, in fact we don’t need to memoize how many moves are remaining. That state can be recovered from other states i.e. the position we are at and how many moves we’ve made to the left. Take a look at my recursive function, it will give you a better idea.