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?

分析：

state: 还剩i个硬币，先取硬币的人的输赢情况（就是题目中说的first player的输赢情况）。

这个题目的条件大概就是，如果取走一个，还剩k - 1个，k - 1个是false，或者如果取走两个，还剩k - 2个，k - 2个是false，那么first player就能保证另一个人走到false的位置上，之后合理出牌就一定会赢。

解法：

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;
        }
        if (n == 1) {
            return true;
        }
        vector<bool> res(n + 1, false);
        res[0] = false;
        res[1] = true;
        res[2] = true;
        for (int i = 3; i < n + 1; i++) {
            if (res[i - 1] == false || res[i - 2] == false) {
                res[i] = true;
            }
        }
        return res[n];
    }
};