Взрыв шариков: интервальный DP в обратном порядке

Даны n шаров со значениями nums. При лопании шара i вы получаете nums[i-1] * nums[i] * nums[i+1] монет — произведение значения самого шара и его текущих соседей. После лопания шара его соседи становятся соседними друг с другом. Найдите максимальное число монет, которое можно получить, лопнув все шары. Наивное моделирование сложно, поскольку при лопании меняются соседи, — обратное интервальное DP элегантно обходит эту трудность.

Если попытаться определить dp[i][j] как максимальное число монет при лопании шаров в диапазоне [i, j] и рассуждать о том, какой шар лопнуть первым, возникает проблема: если первым лопнуть шар k, то nums[k-1] и nums[k+1] должны быть его текущими соседями, но эти шары могут лопнуть позже, из-за чего соседство изменится. Состояние трудно чётко определить при движении вперёд.

Хитрость заключается в том, чтобы рассмотреть, какой шар лопается последним в интервале [i, j]. Когда шар k лопается последним в [i, j], все остальные шары в [i, j] уже исчезли. Поэтому соседями шара k будут ровно nums[i-1] и nums[j+1] — граничные шары непосредственно за пределами интервала. Благодаря этому вычисление монет за последнее лопание становится однозначным: оно не зависит от порядка предыдущих лопаний.

Добавьте фиктивные шары: вставьте 1 в начало и конец nums, чтобы получить nums = [1] + nums + [1]. Определите dp[i][j] как максимальное число монет при лопании всех шаров строго между индексами i и j (исключая границы), где nums[i] и nums[j] — оставшиеся граничные шары. Рекуррентное соотношение: для каждого возможного последнего шара k в (i, j): dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]).

Мы дополняем массив фиктивными шарами, инициализируем таблицу DP нулями (пустой интервал = 0 монет) и заполняем её при возрастании длины интервала. Итоговый ответ — dp[0][n+1], представляющий максимальное число монет при лопании всех исходных шаров с фиктивными шарами в качестве постоянных границ.

Для [3, 1, 5, 8] после добавления фиктивных границ получаем [1, 3, 1, 5, 8, 1] (индексы 0–5). Нас интересует dp[0][5]. Для интервалов длины 2 (внутри находится один шар): dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40. Постепенно заполняя таблицу, получаем оптимальный вариант: лопнуть 1 последним среди {3,1,5,8}, предварительно лопнув соседей, что даёт всего 167 монет.

Существует O(n²) интервалов, и для каждого интервала мы перебираем O(n) точек разделения, поэтому получаем временную сложность O(n³). Объём памяти для таблицы DP составляет O(n²). Для n = 500 шаров это 125 миллионов операций — приемлемо для ограничений на собеседовании. Добавление фиктивных границ упрощает обработку границ: без него потребовались бы явные проверки того, находятся ли i-1 и j+1 в допустимом диапазоне.

То же решение можно записать в нисходящем стиле с помощью @lru_cache; на собеседовании такой вариант может быть интуитивно понятнее при выводе решения. Определите solve(i, j) как максимальное число монет в открытом интервале (i, j). Функция перебирает все варианты k как последнего лопнувшего шара и сохраняет результаты в кэше. Оба подхода имеют одинаковую сложность по времени и памяти.

Распространённая ошибка — определить dp[i][j] как число монет при лопании первого шара в [i,j], а не последнего. Это не работает, поскольку вычисление монет за первое лопание зависит от соседних шаров, которые ещё не лопнули, а состояние этих соседей меняется по мере выполнения алгоритма. При интервальном DP всегда рассматривайте последний элемент, если границы зависят от оставшихся элементов.

Фиктивные значения 1 выбираются потому, что они выступают в роли нейтральных элементов при умножении. Когда граничный шар лопается последним, количество монет равно boundary * last * boundary = 1 * last * 1 = last. Использование 0 дало бы 0 монет, что неверно, а другие значения исказили бы вычисление. Приём с фиктивными значениями единообразно обрабатывает все случаи на границах без отдельных условий для самого левого и самого правого шаров.

В стандартном интервальном DP (задаче о цепном умножении матриц) точка разделения k показывает, где мы делим задачу на две подзадачи, решаемые независимо. В задаче о лопающихся шарах k — это шар, который лопается последним в интервале, поэтому два подинтервала [i,k] и [k,j] становятся независимыми, если считать k всё ещё присутствующим в качестве границы. Именно этот обратный взгляд — ключевая идея, благодаря которой задачу о лопающихся шарах можно решить с помощью интервального DP.

Проверьте, насколько вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», изученные на этом уроке.

В этом уроке Вы узнали: прямая симуляция не работает, потому что лопание шаров непредсказуемо изменяет соседние элементы, обратный подход определяет k как последний шар, лопнувший в интервале, поэтому соседями становятся nums[i] и nums[j], и рекуррентное соотношение dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]) с дополнением фиктивными граничными элементами даёт решение за O(n³). Далее мы переходим к DP для задачи о рюкзаке, начиная с классической задачи о рюкзаке 0/1 и её оптимизации по памяти.