描述

有 n 個硬幣排成一條線。兩個參賽者輪流從右邊依次拿走 1 或 2 個硬幣，直到?jīng)]有硬幣為止。拿到最后一枚硬幣的人獲勝。

請判定 先手玩家 必勝還是必敗?

若必勝, 返回 true, 否則返回 false.

樣例

樣例 1:

輸入: 1
輸出: true
樣例 2:

輸入: 4
輸出: true
解釋: 
先手玩家第一輪拿走一個硬幣, 此時還剩三個.
這時無論后手玩家拿一個還是兩個, 下一次先手玩家都可以把剩下的硬幣拿完.

思路：

令為當前硬幣數(shù)為時先手勝或者敗，如果代表先手勝利，否則代表失敗。先手勝利的條件是后手失敗，那么根據(jù)題意，后手可以表示為和，因此的條件為或者。具體實現(xiàn)如下。

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];
    }
};