1908. Game of Nim

Alice and Bob take turns playing a game with Alice starting first.

In this game, there are n piles of stones. On each player’s turn, the player should remove any positive number of stones from a non-empty pile of his or her choice. The first player who cannot make a move loses, and the other player wins.

Given an integer array piles, where piles[i] is the number of stones in the ith pile, return true if Alice wins, or false if Bob wins.

Both Alice and Bob play optimally.

class Solution {
    unordered_map<int, bool> dp;

    bool helper(int now) {
        if(dp.count(now)) return dp[now];
        bool& res = dp[now] = false;
        for(int i = 1; i <= now; i *= 10) {
            int cur = (now / i) % 10;
            for(int j = 1; j <= cur; j++) {
                if(!helper(now - j * i)) return res = true;
            }
        }
        return res;
    }
public:
    bool nimGame(vector<int>& piles) {
        dp[0] = false;
        int now = 0;
        for(int i = 0; i < piles.size(); i++) now = now * 10 + piles[i];
        return helper(now);
    }
};