There are_n_coins in a line. 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.
Could you please decide the first player will win or lose?
Have you met this question in a real interview?
Yes
Example
Given array A =[3,2,2], returntrue.
Given array A =[1,2,4], returntrue.
Given array A =[1,20,4], returnfalse.
Follow Up Question:
If n is even. Is there any_hacky_algorithm that can decide whether first player will win or lose in O(1) memory and O(n) time?
line 13 , 2d array not easy to pass as parameter, better use 2d vector when passing parameter
can use both iteration and memorialSearch
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<int> &values\) {
// write your code here
if \(values.empty\(\)\) {
return true;
}
int n = values.size\(\);
vector<vector<int> > dp\(n, vector<int>\(n, 0\)\);
vector<vector<int> > sum\(n, vector<int>\(n, 0\)\);
for \(int i = 0; i < n; ++i\) {
dp\[i\]\[i\] = values\[i\];
}
for \(int i = 0; i < n; ++i\) {
int sumSofar = 0;
for \(int j = i; j < n; ++j\) {
sumSofar += values\[j\];
sum\[i\]\[j\] = sumSofar;
}
}
for \(int i = n - 2; i >= 0; --i\) {
for \(int j = i + 1; j < n; ++j\) {
int left = values\[i\] + sum\[i+1\]\[j\] - dp\[i+1\]\[j\];
int right = values\[j\] + sum\[i\]\[j-1\] - dp\[i\]\[j-1\];
dp\[i\]\[j\] = max\(left, right\);
}
}
return dp\[0\]\[n - 1\] > sum\[0\]\[n - 1\] / 2;
}
};