Сложность: 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 {
func winnerSquareGame(_ n: Int) -> Bool {
var cache = [Int: Bool]()
cache[0] = false
return dfs(&cache, n)
}
func dfs(_ cache: inout [Int: Bool], _ remain: Int) -> Bool {
if let result = cache[remain] {
return result
}
let sqrtRoot = Int(Double(remain).squareRoot())
for i in 1...sqrtRoot {
if !dfs(&cache, remain - i * i) {
cache[remain] = true
return true
}
}
cache[remain] = false
return false
}
}Ставь 👍 и забирай 📚 Базу знаний