// Time: O(n^2) // Space: O(n) // DP with rolling window. class Solution { public: /** * @param values: a vector of integers * @return: a boolean which equals to true if the first player will win */ bool firstWillWin(vector &values) { // Even number case. if (values.size() % 2 == 0) { if (firstWinEvenCoins(values)) { return true; } } // Count total. int sum = 0; for (int i = 0; i < values.size(); ++i) { sum += values[i]; } // P[i][n] = max(values[i] + min(P[i + 2][n - 2], P[i + 1][n - 2]), // values[i + n - 1] + min(P[i + 1][n - 2], P[i][n - 2])) vector> P(values.size(), vector(3, 0)); for (int n = 0; n <= values.size(); ++n) { for (int i = 0; i + n - 1 < values.size(); ++i) { int a = i + 2 <= values.size() - 1 && n - 2 >= 0 ? P[i + 2][(n - 2) % 3] : 0; int b = i + 1 <= values.size() - 1 && n - 2 >= 0 ? P[i + 1][(n - 2) % 3] : 0; int c = n - 2 >= 0 ? P[i][(n - 2) % 3] : 0; P[i][n % 3] = max(values[i] + min(a, b), values[i + n - 1] + min(b, c)); } } return P[0][values.size() % 3] > sum - P[0][values.size() % 3]; } // Time: O(n), Space: O(1) // Odd / even numbered strategy for even numbered coins bool firstWinEvenCoins(const vector& values) { int sum = 0; int odd_sum = 0; int even_sum = 0; for (int i = 0; i < values.size(); ++i) { sum += values[i]; if (i % 2 == 0) { odd_sum += values[i]; } else { even_sum += values[i]; } } return odd_sum != even_sum; } }; // Time: O(n^2) // Space: O(n^2) class Solution2 { public: /** * @param values: a vector of integers * @return: a boolean which equals to true if the first player will win */ bool firstWillWin(vector &values) { // Even number case. if (values.size() % 2 == 0) { if (firstWinEvenCoins(values)) { return true; } } // Count total. int sum = 0; for (int i = 0; i < values.size(); ++i) { sum += values[i]; } // P[i][n] = max(values[i] + min(P[i + 2][n - 2], P[i + 1][n - 2]), // values[i + n - 1] + min(P[i + 1][n - 2], P[i][n - 2])) vector> P(values.size(), vector(values.size() + 1, 0)); for (int n = 0; n <= values.size(); ++n) { for (int i = 0; i + n - 1 < values.size(); ++i) { int a = i + 2 <= values.size() - 1 && n - 2 >= 0 ? P[i + 2][n - 2] : 0; int b = i + 1 <= values.size() - 1 && n - 2 >= 0 ? P[i + 1][n - 2] : 0; int c = n - 2 >= 0 ? P[i][n - 2] : 0; P[i][n] = max(values[i] + min(a, b), values[i + n - 1] + min(b, c)); } } return P[0][values.size()] > sum - P[0][values.size()]; } // Time: O(n), Space: O(1) // Odd / even numbered strategy for even numbered coins bool firstWinEvenCoins(const vector& values) { int sum = 0; int odd_sum = 0; int even_sum = 0; for (int i = 0; i < values.size(); ++i) { sum += values[i]; if (i % 2 == 0) { odd_sum += values[i]; } else { even_sum += values[i]; } } return odd_sum != even_sum; } }; // Time: O(n^2) // Space: O(n^2) class Solution3 { public: /** * @param values: a vector of integers * @return: a boolean which equals to true if the first player will win */ bool firstWillWin(vector &values) { // Even number case; if (values.size() % 2 == 0) { if (firstWinEvenCoins(values)) { return true; } } // P[i][j] = max(values[i] + min(P[i + 2][j], P[i + 1][j - 1]), // values[j] + min(P[i + 1][j - 1], P[i][j - 2])) vector> P(values.size(), vector(values.size(), 0)); int sum = 0; for (int i = 0; i < values.size(); ++i) { sum += values[i]; for (int m = 0, n = i; n < values.size(); ++m, ++n) { int a = m + 2 <= values.size() - 1 ? P[m + 2][n] : 0; int b = m + 1 <= values.size() - 1 && n - 1 >= 0 ? P[m + 1][n - 1] : 0; int c = n - 2 >= 0 ? P[m][n - 2] : 0; P[m][n] = max(values[m] + min(a, b), values[n] + min(b, c)); } } return P[0][values.size() - 1] > sum - P[0][values.size() - 1]; } // Time: O(n), Space: O(1) // Odd / even numbered strategy for even numbered coins bool firstWinEvenCoins(const vector& values) { int sum = 0; int odd_sum = 0; int even_sum = 0; for (int i = 0; i < values.size(); ++i) { sum += values[i]; if (i % 2 == 0) { odd_sum += values[i]; } else { even_sum += values[i]; } } return odd_sum != even_sum; } };

Problem