Coins In A Line

4, Conis in A Line

有5个币，A和B轮流行动，每次能拿1或者2个币，判断A先手能否获胜。

```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
    vector<bool> dp(n+1, false);
    vector<bool> flag(n+1, false);
    return memSearch(dp, flag, n);
}

int memSearch(vector<bool>& dp, vector<bool>& flag, int n)
{
    if(flag[n] == true)
    {
    //cout<<n<<" "<<dp[n]<<endl;
        return dp[n];
    }

    if(n == 0)
    {
        dp[n] = false;
        return false;
    }
    else if(n == 1)
    {
        dp[n] = true;
        return true;
    }
    else if(n == 2)
    {
        dp[2] == true;
        //return true;
    }
    else
    {   
        if(memSearch(dp, flag, n-1) == false || memSearch(dp, flag, n-2) == false)
        {
            dp[n] = true;
        }
        else
        {
            dp[n] = false;
        }

        //dp[n] = !memSearch(dp, flag, n-1) || !memSearch(dp, flag, n-2);
    }

    flag[n] = true;
    //cout<<n<<" "<<dp[n]<<endl;
    return dp[n];

}

};```