LeetCode 1140. Stone Game II: разбор за секунды | Рекурсия | 4 шага динамического программировани...

LeetCode 1140. В задаче «Игра в камни II» Алиса и Боб должны взять первые X куч камней, где X всегда находится в диапазоне от 1 до 2M. Жадный алгоритм не справляется с этой задачей динамического программирования в теории игр. Если взять самые большие кучи в начале, M увеличивается, что дает Бобу более широкий диапазон значений X на следующем ходу. Правильное решение — это одна рекурсивная функция плюс двумерная таблица мемоизации. Большинство объяснений задачи LeetCode 1140 сразу переходят к коду. Они пропускают объяснение, почему жадный алгоритм не работает и почему для состояния динамического программирования нужны только две переменные: индекс и M. В «Игре в камни I» ответ состоял из одной строки: вернуть true. «Игра в камни II» — другая задача. Здесь нет коротких путей. Необходимо вернуть максимальное количество камней, которое Алиса может собрать, при этом Боб играет оптимально. Массив куч может содержать до 100 значений, поэтому обычная рекурсия приводит к таймауту. Мемоизация решает эту проблему. В этом видео подробно разбирается игра в «Камни II» с полным пробным запуском примера, где выбор 7 и 9 первыми приводит к обратным результатам. Затем пошагово строится рекурсия solve(index, M). Вы узнаете формулу пиццы: ваш счет равен общему количеству оставшихся камней минус лучший камень, который может взять противник. Вы увидите базовый случай, когда индекс достигает длины массива, цикл, где X изменяется от 1 до 2M, новое значение M, вычисленное как max(X, M), и окончательный ответ как максимум по каждому выбору. Наконец, мы преобразуем простую рекурсию в мемоизированную 2D-версию динамического программирования, заполняем ее минус 1 с помощью Arrays.fill, отправляем результат и проходим ежедневное задание LeetCode. Разделы: 00:00 — Зацепка: Краткий обзор игры в камни 1 и верный однострочный ответ на задачу 01:08 — LeetCode 1140 Игра в камни II: Условные положения 03:11 — Правила игры: Возьмите X стопок от 1 до 2M, и M становится max(M, X) 05:44 — Игра в камни 1 против игры в камни 2: Что на самом деле меняется 06:05 — Пример: Почему жадный выбор 7 и 9 НЕ РАБОТАЕТ 07:11 — Интуиция: Одна рекурсивная функция решения решает задачу 09:00 — Состояние динамического программирования: Только индекс и M, нет переменной хода 10:38 — Формула пиццы: Мой счет равен оставшемуся минус счет противника 13:20 — Шаг второй: Суммирование оставшихся камней от индекса до конца 15:00 — Рекуррентное соотношение: Вызов противника и новое M = max(x, M) 16:40 — Разбор кода на Java: Total Stones и цикл выбора 20:00 — Почему рекурсия приводит к превышению лимита времени выполнения и мемоизации с помощью двумерного массива динамического программирования 23:20 — Финальная отправка, 30-дневная серия и заключение Полный код: https://github.com/Shaanworkspace/YOU... Больше от Shaan Labs: Ежедневные решения LeetCode → https://github.com/Shaanworkspace/YOU... Плейлист LeetCode →    • LeetCode Daily Challenge | Java Solutions   Видео по игре в камни 1 →    • Leetcode 877. Stone Game | Recursion to DP...   Видео по игре в камни 3 →    • Leetcode 1406. Stone Game III | DP Solutio...   Часто задаваемые вопросы: Что такое игра в камни 1140 на LeetCode II? Игра в камни 1140 на LeetCode II — это задача на динамическое программирование в теории игр. Алиса и Боб по очереди убирают первые X стопок камней, где X может принимать любое значение от 1 до 2M. M начинается с 1 и становится max(M, X) после каждого хода. Верните максимальное количество камней, которое Алиса может собрать, если оба игрока играют оптимально. Как решить игру в камни II на Java? Напишите рекурсивную функцию solve(index, M), которая возвращает максимальное количество камней, которое текущий игрок может собрать от index до конца. Переберите все X от 1 до 2M, пусть противник вызовет solve(index + X, max(X, M)), и установите свой счет равным totalRemaining минус лучший результат противника. Кэшируйте каждый результат в двумерном массиве динамического программирования, заполненном минус 1. Почему жадный алгоритм не работает в игре в камни II? Жадный ход не срабатывает, потому что взятие самых больших куч первым увеличивает M для следующего игрока. Если Алиса сразу возьмет 7 и 9, новое M увеличится, поэтому Боб сможет взять еще больше куч на своем следующем ходу. Локальный максимум не гарантирует глобального максимума для Алисы. Каково состояние динамического программирования в игре «Камни II»? Состояние динамического программирования — (индекс, M). Индекс — это позиция в массиве куч, с которой начинается текущий ход, а M — максимальное количество куч, которое может взять текущий игрок. Базовый случай — когда индекс достигает длины массива, когда камней не остается, и счет равен нулю. Какова временная и пространственная сложность мемоизированного решения? Мемоизированная рекурсия хранит один результат для каждой пары (индекс, M), что составляет O(n²) пространства. Каждое состояние перебирает до 2M вариантов выбора X, поэтому время в худшем случае составляет O(n³), и поскольк...