$$x = y$$Coins in a Line
There are n coins in a line. Two players take turns to take one or two coins from right side until there are no more coins left. The player who take the last coin wins.
Could you please decide the first play will win or lose?
S1: DFS
对于先手来说，只要当前取1或2能获胜即可。
- 若取1，后手随后可取1或2，下一次先手取子还剩n-1-1=n-2和n-1-2=n-3这两种情况必须全部获胜才可能获胜
- 若取2，后手随后可取1或2，下一次先手取子还剩n-2-1=n-3和n-2-2-n-4这两种情况也必须获胜
f[n] = (f[n-2]&&f[n-3]) || (f[n-3]&&f[n-4])
bool firstWillWin(int n) {
if (n <= 0 || n == 3) return false;
if (n == 1 || n == 2) {
return true;
}
return (firstWillWin(n - 2) || firstWillWin(n - 4)) &&firstWillWin(n - 3);
}
S2: DP避免重复计算
也可用记忆化搜索剪支
bool firstWillWin(int n) {
if (n == 0 || n ==3) {
return false;
}
if (n < 3) {
return true;
}
vector<bool> win(n + 1, false);
win[0] = true;
win[1] = true;
win[2] = true;
win[3] = false;
for (int i = 4; i <= n; ++i) {
win[i] = (win[i-2] || win[i-4]) && win[i-3];
}
return win[n];
}
Coins in a Line II
There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.
Could you please decide thefirstplayer will win or lose?
S:DP O(n)
firstSum[i]存储以i起手能获得的最大合
class Solution {
public:
bool firstWillWin(vector<int> &values) {
n = values.size();
if (n == 0) {
return false;
}
if (n < 3) {
return true;
}
int sum = 0;
for (int i : values) {
sum += i;
}
firstSum = vector<int>(n, 0);
visited = vector<bool>(n, false);
firstSum[n-1] = values[n-1];
firstSum[n-2] = values[n-2] + values[n-1];
visited[n-1] = true;
visited[n-2] = true;
dfs(values, 0);
return sum - firstSum[0] < firstSum[0];
}
int dfs(vector<int>& values, int cur) {
if (cur >= n) {
return 0;
}
if (visited[cur]) {
return firstSum[cur];
}
firstSum[cur] = max(min(dfs(values, cur + 2), dfs(values, cur + 3)) + values[cur],
min(dfs(values, cur + 3), dfs(values, cur + 4)) + values[cur]
+ values[cur+1]);
visited[cur] = true;
return firstSum[cur];
}
private:
vector<bool> visited; //可以直接用first sum判断visited，另开一个数组只是为了方便
vector<int> firstSum;
int n;
};
Coins in a Line III
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?
S: 区间型DP O(n^2)
maxSum[i][j]表示在i,j区间内先手能得到的最大硬币值之和
class Solution {
public:
bool firstWillWin(vector<int> &values) {
int n = values.size();
int sum = 0;
for (int i : values) {
sum += i;
}
visited = vector<vector<bool>>(n, vector<bool>(n, false));
maxSum = vector<vector<int>>(n, vector<int>(n));
int firstSum = dfs(values, 0, n-1);
return firstSum > sum - firstSum;
}
int dfs(vector<int>& values, int i, int j) {
if (i > j) {
return 0;
}
if (visited[i][j]) {
return maxSum[i][j];
}
if (j - i <= 1) {
maxSum[i][j] = max(values[i], values[j]);
visited[i][j] = true;
return maxSum[i][j];
}
int sum1 = min(dfs(values, i + 2, j), dfs(values, i + 1, j - 1)) + values[i];
int sum2 = min(dfs(values, i + 1, j - 1), dfs(values, i, j - 2)) + values[j];
maxSum[i][j] = max(sum1, sum2);
visited[i][j] = true;
return maxSum[i][j];
}
private:
vector<vector<bool>> visited;
vector<vector<int>> maxSum;
};
486. Predict the Winner
Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.
Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.
Example 1:
Input:
[1, 5, 2]
Output:
False
Explanation:
Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.
Example 2:
Input:
[1, 5, 233, 7]
Output:
True
Explanation:
Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
- Any scores in the given array are non-negative integers and will not exceed 10,000,000.
- If the scores of both players are equal, then player 1 is still the winner.
S： dp O(n^2)
dp[i][j]存储对于第i到j个元素先手与后手的得分之差
初始化：i == j时dp[i][i] = nums[i]
状态转移方程：dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
bool PredictTheWinner(vector<int>& nums) {
int n = nums.size();
if (n & 1 == 0) return true; //若是偶数个，先选的人一定可以得到所有奇数位和或所有偶数位和，只要选择奇偶和中大的那个即可
vector<vector<int>> dp(n, vector<int>(n));
for (int len = 0; len < n; ++len) {
for (int i = 0; i < n - len; ++i) {
int j = i + len;
if (len == 0) dp[i][j] = nums[i];
else dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}