LintCode "Coins in a Line"

class Solution {
    unordered_map<int, bool> cache;
public:
    bool go(int n)
    {
        if (n <=0) return false;
        if (n < 3) return true;

        if(cache.find(n) == cache.end())
        {
            cache[n] = !go(n - 1) || !go(n - 2);
        }
        return cache[n];
    }
    /**
     * @param n: an integer
     * @return: a boolean which equals to true if the first player will win
     */
     bool firstWillWin(int n) {
        return go(n);
    }
};