The Problem
We have a line of things to take. Each thing has a value , 2 players are playing each of them is taking either the first element or the last , we are the first one, the second player takes the maximum of the first and last. How many points we can score if we play the best way?
Solution
We will solve this using the dynamic programming. We have an array A[N][N] where A[i][j] shows the answer for a segment of the given items from i to j. Suppose the name of the given array is a. So initially A[i][i]=a[i] because form i to i there is only one element and we will take that and end the game. Then, every A[i][i+1] equals to max(a[i], and a[i+1]) because when there are 2 elements we would rather take the biggest and then the second one will take the last and the game will end. Now, suppose we have an answer for A[i][j] and we want to find A[i][j+1] in other words when we have already found for a segment from i to j now when the j+1th element is added what will the answer be? When the new element a[j+1] is added we have 2 options
1. Take the new added element and then the second player will take the biggest from a[i] and a[j] and we will have to play our best for either for a segment i+1 to j or for a segment i to j-1 both we have calculated previously.
2. We can take the i the element and then the second player will take the bigger from a[i+1] and a[j+1] and then like in the previous option we will add already calculated answer.
There is a task on SPOJ which requires the knowledge of this, you might want to try this and here is the full source code.
No comments:
Post a Comment