Анализ:

Этот вопрос дает нам число для начала и спрашивает, можем ли мы выиграть игру любым возможным способом, стратегически забирая 1, 2 или 3 камня за раз.

Пока что мы знаем, что если мы получим 1, 2 или 3 камня в свой ход, мы выиграем.

Теперь давайте рассмотрим несколько примеров, чтобы увидеть, сможем ли мы найти какую-либо закономерность.

Как показано на рисунке выше, мы проигрываем, если получаем 4, независимо от того, берем ли мы 1, 2 или 3 камня, компьютер всегда будет выбирать последним.

Однако, если мы получим 5 камней, я возьму только 1 камень и 4 отдам компьютеру. Таким образом, компьютер не сможет выиграть (см. пример с 4 камнями).

С помощью аналогичного анализа мы выяснили, что если выпадет 1, 2, 3, 5, 6, 7, 9, мы выиграем, а если выпадем 4, 8, то проиграем. Следовательно, очевидно, что нам нужно проверить, делится ли число на 4, мы ПРОИГРЫВАЕМ!

Из анализа приведенных выше примеров мы можем сделать вывод, что это проблема жадного алгоритма.

Жадный алгоритм – это простой интуитивно понятный алгоритм, который используется в задачах оптимизации. Алгоритм делает оптимальный выбор на каждом этапе, пытаясь найти общий оптимальный способ решения всей задачи. Жадные алгоритмы довольно успешно решают некоторые задачи, такие как кодирование Хаффмана, которое используется для сжатия данных, или алгоритм Дейкстры, который используется для поиска кратчайшего пути через граф.

Подробнее:https://brilliant.org/wiki/greedy-algorithm/

Динамическое программирование и жадный подход

Жадный алгоритм — это алгоритмическая парадигма, которая строит решение по частям, всегда выбирая следующую часть, которая предлагает наиболее очевидную и непосредственную выгоду. Таким образом, проблемы, в которых выбор локально оптимального также приводит к глобальному решению, лучше всего подходят для Greedy.

Например, рассмотрим задачу о дробном рюкзаке. Локальная оптимальная стратегия состоит в том, чтобы выбрать предмет, который имеет максимальное соотношение стоимости и веса. Эта стратегия также приводит к глобальному оптимальному решению, потому что мы разрешили брать части элемента.

Динамическое программирование — это в основном оптимизация простой рекурсии. Везде, где мы видим рекурсивное решение с повторными вызовами одних и тех же входных данных, мы можем оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы просто хранить результаты подзадач, чтобы нам не приходилось пересчитывать их позже, когда это потребуется. Эта простая оптимизация снижает сложность времени с экспоненциальной до полиномиальной. Например, если мы напишем простое рекурсивное решение для чисел Фибоначчи, мы получим экспоненциальную временную сложность, а если мы оптимизируем его, сохраняя решения подзадач, временная сложность уменьшится до линейной.

Для получения дополнительной информации: https://www.geeksforgeeks.org/greedy-approach-vs-dynamic-programming/

Решение 1. Условная логика — Время: O(1), Пространство: O(1)

Как объяснялось в разделе «Анализ», код преобразуется в код, представленный ниже.

Временная сложность этого решения составляет O (1), поскольку мы используем только один условный оператор.

Сложность пространства этого решения также составляет O (1), поскольку мы не используем дополнительное хранилище.

Время выполнения на Leetcode было удовлетворительным.

Время выполнения: 0 мс, быстрее, чем 100,00 % онлайн-отправлений Java для Nim Game.

Использование памяти: 36,5 МБ, менее 7,69 % от всего количества онлайн-заявок на Java для Nim Game.