变型：如果是最后拿走所有石子那个人输，则f[0] = true
394. Coins in a Line
dp[n]表示n个石子，先手的人，是必胜还是必输。拿1个石子，2个石子之后都是必胜，则当前必败；拿1个石子，2个石子之后都是必败，则当前必胜；如果拿1个石子，2个石子之后有必败，则当前必胜。
class Solution {
public:
/**
* @param n: An integer
* @return: A boolean which equals to true if the first player will win
*/
bool firstWillWin(int n) {
// write your code here
if(n == )
return false;
if(n == )
return true;
vector<int> dp(n+);
dp[] = false,dp[] = true;
for(int i = ;i <= n;i++){
if(dp[i-] == true && dp[i-] == true)
dp[i] = false;
else if(dp[i-] == false && dp[i-] == false)
dp[i] = true;
else
dp[i] = dp[i-] || dp[i-];
}
return dp[n];
}
};
292. Nim Game
这个题几乎与Coins in a Line一模一样。
解法一：
这个解法超内存了
class Solution {
public:
bool canWinNim(int n) {
if(n == )
return false;
if(n == || n == )
return true;
vector<int> dp(n+);
dp[] = false,dp[] = true,dp[] = true;
for(int i = ;i <= n;i++){
if(dp[i-] == true && dp[i-] == true && dp[i-] == true)
dp[i] = false;
else if(dp[i-] == false && dp[i-] == false && dp[i-] == false)
dp[i] = true;
else
dp[i] = true;
}
return dp[n];
}
};
解法二：
因为只与前3个有关系，所以用变量替代，能不超内存，但超时了
class Solution {
public:
bool canWinNim(int n) {
if(n == )
return false;
if(n == || n == )
return true;
bool num1 = false,num2 = true,num3 = true;
for(int i = ;i <= n;i++){
bool tmp;
if(num1 == true && num2 == true && num3 == true){
tmp = false;
}
else
tmp = true;
num1 = num2;
num2 = num3;
num3 = tmp;
}
return num3;
}
};
解法三：
过
class Solution {
public:
bool canWinNim(int n) {
return n% ? true : false;
}
};
395. Coins in a Line II
https://www.cnblogs.com/grandyang/p/5864323.html
与Coins in a Line相同的是，这个题每次也只能拿一个或者两个。不同的是，最终的胜负是谁拥有的金币的价值更多。
dp[i]表示从i到end可取的最大钱数
如果取一个，dp[i] = values[i] + min(dp[i+2],dp[i+3])
如果取两个，dp[i] = values[i] + values[i+1] + min(dp[i+3],dp[i+4])
所以最终的递归就是dp[i] = max(values[i] + min(dp[i+2], dp[i+3]), values[i] + values[i + 1] + min(dp[i+3], dp[i+4]))
代码实际上是可以解决n = 1和n = 2的情况，只是因为n-2，n-3这种会造成越界的错误。
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
int n = values.size();
if(n <= )
return true;
vector<int> dp(n+,);
dp[n-] = values[n-];
dp[n-] = values[n-] + values[n-];
dp[n-] = values[n-] + values[n-];
for(int i = n - ;i >= ;i--)
dp[i] = max(values[i] + min(dp[i+],dp[i+]),values[i] + values[i+] + min(dp[i+],dp[i+]));
int sum = ;
for(int i = ;i < n;i++)
sum += values[i];
return dp[] > sum - dp[];
}
};