Dynamic Programming Question

#1

Can someone kindly explain to me the below solution for the given question in detail and how and why it works, please?

Question Link: https://techbomb.net/max-sum-codevita-solution-2020/

Solution(Correct): https://ideone.com/eSvDWr

#2

Okay I will see to it and explain it as soon as possible

#3

Thanks… Will be waiting.

#4

Okay I have seen the code, in which lines you are facing issue?
On a broad scale it is using DP to solve the question along with using the facts already provided like x and d
Apart from that some new keywords like accumulate have been used which may be a cause of why you are finding it difficult to understand.
Just search up accumulate function on the net, its just an aggregator function.

#6

The first loop is inserting an element extra because that is the final element that gives the answer in a dp problem. So for an array of size n, the dp will be of the size n+1 because the last element is calculating the dp for the whole array (think of it as a function call that gets a return value for the whole array passed as a parameter)
In the first we are just adding the elements of the array in dp and dp_x. (game initialization)
In the next loop we are increasing the value of dp based on player strategy.
So it is starting from x+2 as we have to skip one element
then dp is updated based on the starting value of the previous player. The corresponding element is removed from your dp_x and replaced with the new dp value.
finally in the third loop the winner is decide based on who took maximum sum. (that means minimum ans as we are subtracting it from total)

1 Like
#7

Both the players are playing independently of each other then why is “dp is updated based on the starting value of the previous player.”? And can you please explain based on what logic the corresponding element is removed and the new element is added, please?

And for example, in Palindromic substring question… the 2D matrix is storing whether the string starting from ith index to jth index is palindrome or not. What is the array dp and multiset dp_x exactly storing here?

#8

No both players are not playing independently but with an optimal strategy to win, so moves of other player needs to be taken into account.
Example , in chess both players strategy depends on the moves made by the other player and are not independent.
The logic is to maximise the sum, so if the previous player has got a bigger move updated you remove your smaller one to keep yourself in the game.
Dp is storing the sum of the player if the stones lie in that range.
multiset is storing the possibilites from there for the other player and choosing the maximum from that to keep yourself winning.