Someone please suggest a way to precede these kind of problems! I am a lot interested but a beginner programmer! (knows only basics)
If you are new to these types of problems, refer this link.
See the question is simple dp
n matches you a(1),a(2),a(3)…a(n)
So now what will be the total number of selection of matches a player can play 2^n.
However we have one more constraint that is a player can’t play 3 matches in a row thus it is clear that brute force won’t be suffice and would definitely time out… Hence what we can do is analyze the problem on smaller values of n (actually this is the first step one should follow when dealing with such problems)
So lets for n=4
5 6 3 10
So now what can we do
We can pick first match that is 5
Then second that is 6 and then 4rth that is 10 getting total of 21. Getting any hints want am I doing!
Lets observe the solution
So there will be two types of solution one having a(1) and other not having a(1)
So if write a function
F(a,b) where a is the match under our observation (we would be iterating the matches one by one) and b the left matches we can continuously play.
So if we take a(1) we can play only one match more in continuity (no 3 matches in a row)
Hence after taking a(1) we can either take a(2) or again start the problem starting from a(3)
So the function
Now here maximum value of b=2 hence time complexity would be 2a ie suffice. We are taking b=2 because we can play at most 2 matches in a row
Let’s take example
F(1,2) for matches 5,4,10,7
So now keep on doing like this for all f(a,b) needed and obtain the answer… Note f(a,0)=0 because if we can play 0 matches in continuity then value if also 0
Hope it clears your problem
Well that was hell lot but I experienced problems with dp too hence I am helping you with such a large explanation.
Hope it help.
thanks a lot man! got the logic…
But could you please send me the complete code for the solution of this problem. @japoorv
Buddy add me on Google plus and I would help you to write the code
Okay here’s the solution:
Keep Fees=0 and store the numbers from 1 to N
The final solution would be stored at