Сложность: 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.
😎 Решение:
class Solution {
public boolean winnerSquareGame(int n) {
HashMap<Integer, Boolean> cache = new HashMap<>();
cache.put(0, false);
return dfs(cache, n);
}
public boolean dfs(HashMap<Integer, Boolean> cache, int remain) {
if (cache.containsKey(remain)) {
return cache.get(remain);
}
int sqrt_root = (int) Math.sqrt(remain);
for (int i = 1; i <= sqrt_root; i++) {
if (!dfs(cache, remain - i * i)) {
cache.put(remain, true);
return true;
}
}
cache.put(remain, false);
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний