描述
有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。
请判定 先手玩家 必胜还是必败?
若必胜, 返回 true, 否则返回 false.
样例
样例 1:
输入: 1
输出: true
样例 2:
输入: 4
输出: true
解释:
先手玩家第一轮拿走一个硬币, 此时还剩三个.
这时无论后手玩家拿一个还是两个, 下一次先手玩家都可以把剩下的硬币拿完.
思路：
令为当前硬币数为
时先手胜或者败，如果
代表先手胜利，否则代表失败。先手胜利的条件是后手失败，那么根据题意，后手可以表示为
和
，因此
的条件为
或者
。具体实现如下。
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==0)
{
return false;
}
vector<bool> dp(n+1,false);
dp[1]=true;
dp[2]=true;
for(int i=3;i<=n;i++)
{
if(!dp[i-1] || !dp[i-2])
{
dp[i]=true;
}
else
{
dp[i]=false;
}
}
return dp[n];
}
};
