Can somebody please tell me approach for this problem…I know it has to be solved with Dynamic Programming.But I am just a beginner So a detailed explanation will be helpful.Please help fellow coders.
Hey Buddy, I know I am late answering the question! Is the problem solved or I can explain?
Please explain , I am new to competitive programming . I am not understanding the term “Next, there are h lines of inputs. The ith line of these, specifies the number of philosopher’s stones in each tile of the ith row from the front”.
Hey! A bit late but for people who come here after me. This is a simple problem. Just think of the recursion relation. Once you have done that start with the last row going to the first one and apply the recursion relation on every element in the way. Then finally select the maximum element from the first row. Give it some time and it will be easy. I wont tell everything otherwise what’s the fun to code. Happy Coding.
Well, you know that the problem can be solved using dynamic programming. But wait, do you know why DP for this problem.
You need to find the maximum stones that can be collected. So if you use brute force in some smarter way that is the solution to the problem.
Now consider this example.
1+1+1+1+1+1+1+1+1 ,how much? 9 right. Now add another +1 to the previous sequence, how much? 10 right. But how did you know so fast? I think you got me.
Now consider all the possible directions you can collect stone from and save their answers so that you can use them later.
Now you can solve this problem easily.
Still, in doubt, feel free to ask again.