Here is code for inputs up to NMAX long. With more fiddling, you
could easily get the storage requirement down to O(n).
#include <stdio.h>
#define NMAX 100
int min(int x, int y) { return x < y ? x : y; }
int best_score(int *notes, int n)
{
int F[NMAX][NMAX], i, j, d;
for (i = 0; i < n; i++)
F[i][i] = notes[i];
// Compute the summations efficiently.
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
F[i][j] = F[i][j - 1] + notes[j];
// Complete the DP values
for (d = 1; d < n; d++)
for (i = 0; i < n - d; i++) {
j = i + d;
F[i][j] -= min(F[i + 1][j], F[i][j - 1]);
}
return F[0][n - 1];
}
int main(void)
{
int notes[] = {2,5,7,1,8,9};
printf("best is %d\n", best_score(notes, sizeof notes / sizeof
notes[0]));
return 0;
}
On Oct 7, 11:43 pm, Gene <[email protected]> wrote:
> Nice problem. Let N_1, N_2, ... N_n be the values of the N notes.
> Let F(i,j) be the maximum possible score the current player can get
> using only notes i through j. Then
>
> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
>
> This is saying that the current player always makes the choice that
> minimizes B the best score that the other player can achieve. When we
> know that choice, the best _we_ can do is the sum of all the available
> notes minus B.
>
> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
> where i > j.
>
> For example, suppose we have notes 3 7 2 1 . The answer we want is
> F(1,4).
>
> Initially we have
> F(1,1) = 3
> F(2,2) = 7
> F(3,3) = 2
> F(4,4) = 1
>
> Now we can compute
> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
> F(2,3) = 9 - min(F(3,3), F(2,2)) = 9 - min(2,7) = 7 (pick N_2=7).
> F(3,4) = 3 - min(F(4,4), F(3,3)) = 3 - min(1,2) = 2 (pick N_3=2).
> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
>
> On Oct 7, 8:14 pm, Anand <[email protected]> wrote:
>
>
>
> > Given a row of notes (with specified values), two players play a game. At
> > each turn, any player can pick a note from any of the two ends. How will the
> > first player maximize his score? Both players will play optimally.- Hide
> > quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
