Coins in a Line | LeetCode

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.

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

A Better Solution:

Let us look one extra step ahead this time by considering the two coins the opponent will possibly take, A_i+1 and A_j. If the opponent takes A_i+1, the remaining coins are { A_i+2 … A_j }, which our maximum is denoted by P(i+2, j). On the other hand, if the opponent takes A_j, our maximum is P(i+1, j-1). Since the opponent is as smart as you, he would have chosen the choice that yields the minimum amount to you.

Therefore, the maximum amount you can get when you choose A_i is:

P1 = Ai + min { P(i+2, j), P(i+1, j-1) }

Similarly, the maximum amount you can get when you choose A_j is:

P2 = Aj + min { P(i+1, j-1), P(i, j-2) }

Therefore,

P(i, j) = max { P1, P2 }
        = max { Ai + min { P(i+2, j),   P(i+1, j-1) },
                Aj + min { P(i+1, j-1), P(i,   j-2) } }

We can store values of Sum{A_i … A_j} in a table and avoid re-computations by computing in a certain order.

If you notice, we do not need to build complete matrix but only need to build right (upper) triangular matrix. Also notice that C[i, i] (diagonal elements) will always be equal to A[i]. Below is the code which runs in O(n^2) time and takes O(n^2) space.

const int MAX_N = 100;

int maxMoney(int A[], int N) {

  int P[MAX_N][MAX_N] = {0};

  int a, b, c;

  for (int i = 0; i < N; i++) {

    for (int m = 0, n = i; n < N; m++, n++) {

      assert(m < N); assert(n < N);

      a = ((m+2 <= N-1)             ? P[m+2][n] : 0);

      b = ((m+1 <= N-1 && n-1 >= 0) ? P[m+1][n-1] : 0);

      c = ((n-2 >= 0)               ? P[m][n-2] : 0);

      P[m][n] = max(A[m] + min(a,b),

                    A[n] + min(b,c));

    }

  }

  printMoves(P, A, N);

  return P[0][N-1];

}

void printMoves(int P[][MAX_N], int A[], int N) {

  int sum1 = 0, sum2 = 0;

  int m = 0, n = N-1;

  bool myTurn = true;

  while (m <= n) {

    int P1 = P[m+1][n]; // If take A[m], opponent can get...

    int P2 = P[m][n-1]; // If take A[n]

    cout << (myTurn ? "I" : "You") << " take coin no. ";

    if (P1 <= P2) {

      cout << m+1 << " (" << A[m] << ")";

      m++;

    } else {

      cout << n+1 << " (" << A[n] << ")";

      n--;

    }

    cout << (myTurn ? ", " : ".\n");

    myTurn = !myTurn;

  }

  cout << "\nThe total amount of money (maximum) I get is " << P[0][N-1] << ".\n";

}

Assume that your opponent is so dumb that you are able to manipulate him into choosing the coins you want him to choose. Now, what is the maximum possible amount of money you can win?
Also refer to http://tech-queries.blogspot.com/2011/06/get-maximum-sum-from-coins-in-line.html
Read full article from Coins in a Line | LeetCode