Задача: 1510. Stone Game IV
Сложность: hard

Алиса и Боб поочередно играют в игру, причем Алиса начинает первой.

Изначально в куче n камней. В ходе каждого хода игрок удаляет любое ненулевое количество камней, являющееся квадратом целого числа.

Кроме того, если игрок не может сделать ход, он/она проигрывает игру.

Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

👨‍💻 Алгоритм:

1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях.

2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs.

3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True.

😎 Решение:

var winnerSquareGame = function(n) {
    const cache = new Map();
    cache.set(0, false);

    const dfs = (remain) => {
        if (cache.has(remain)) {
            return cache.get(remain);
        }
        const sqrtRoot = Math.floor(Math.sqrt(remain));
        for (let i = 1; i <= sqrtRoot; i++) {
            if (!dfs(remain - i * i)) {
                cache.set(remain, true);
                return true;
            }
        }
        cache.set(remain, false);
        return false;
    };

    return dfs(n);
};

Ставь 👍 и забирай 📚 Базу знаний