Coins in a line

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Would you rather go first or second? Does it matter?
Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

01 void maxCoin(int *A,int start, int end, vector <int*>& B)
02 {
03     if(start==end){
04         B[start][end]=A[start];
05         return;
06     }
07     int m=0;
08     for(int i=start;i<=end;i++)
09         m+=A[i];
10     int a=B[start+1][end];
11     int b=B[start][end1];
12     int result=a>b?b:a;
13     B[start][end]=mresult;
14 }
16 int maxCoinT(int *A, int size)
17 {
18     vector <int*> B(size);
19     for(int i=0;i<size;i++)
20         B[i]=new int[size];
21     for(int i=0;i<size;i++)
22         for(int j=0;j<size;j++)
23             B[i][j]=0;
25     for(int i=0;i<size;i++){
26         for(int j=0;j<size;j++){
27             if(j+i<size)
28                 maxCoin(A,j,j+i,B);
29         }
30     }
31     return B[0][size1];
32 }
This entry was posted in Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s