Burst Balloons

Q: Какова временная сложность задачи «Взрывающиеся шарики»?

Время O(n³) и память O(n²) : около n²/2 промежутков, в каждом из которых пробуем до n шаров в качестве последнего. Для 300 шаров это около 4.5 × 10^6 шагов. Перебор всех порядков — O(n · n!) .

СложноДинамическое программирование

+10

Дан ряд воздушных шаров в виде nums, где nums[i] — число на шаре i. Нужно лопнуть все шары по одному в любом порядке. За лопнувший шар начисляется left × nums[i] × right монет, где left и right — числа на его текущих соседях, ближайших шарах с каждой стороны, которые всё ещё находятся в ряду. Если соседа нет, его значение считается равным 1. После того как шар лопается, два его соседа становятся соседними. Верните максимальное количество монет, которое можно собрать.

Функция

maxCoins(nums: integer-array) → integer

numsinteger-array: числа на шариках, слева направо
Возвращаетinteger: максимальное количество монет, которое можно собрать, лопнув все воздушные шарики

Ограничения

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
Ответ меньше 3 × 10⁸, поэтому он помещается в 32-битное целое число со знаком.

Примеры

Ввод: nums = [2, 4, 3]
Вывод: 33
Пояснение: Разбейте 4 на 2 × 4 × 3 = 24. 2, теперь стоящая рядом с 3, дает 1 × 2 × 3 = 6, а 3 дает 3: всего 33.

Дополнительный вопрос

Можешь также вернуть один порядок взрывания, который приносит больше всего монет?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждый лопнувший шарик меняет порядок соседства, поэтому первый лопнувший шарик не разделяет ряд: его два соседа становятся соседями друг для друга. Разделяет ряд последний лопнувший шарик на отрезке. Он остаётся, когда все остальные уже лопнули, поэтому отрезки по обе стороны от него независимы, и таблица интервалов по отрезкам решает задачу за O(n³).

Попробуйте все порядки взрывания

Верно, но не успевает на самых больших тестах

Идея

Выбери воздушный шар, вычисли left × value × right, удали его и реши укороченный ряд тем же способом, сохраняя наилучшую сумму для каждого выбора. Этот метод перебирает все порядки, поэтому он корректен.

Для первого лопнувшего шара есть n вариантов, для следующего — n-1 и так далее: всего n! порядков, уже 479,001,600 для 12 воздушных шаров. Запоминание результатов для каждого множества оставшихся шаров не помогает, поскольку таких множеств 2^n.

Алгоритм

Напиши burstAll(row): максимальное количество монет из шаров в row, 0 для пустого ряда.
Для каждой позиции k получи left × row[k] × right, используя 1 за каждым из концов, плюс результат burstAll для ряда без row[k].
Верни наилучшую сумму для всех k и вызови burstAll(nums).

def maxCoins(nums):
    # Most coins you can still collect from the balloons in row
    def burst_all(row):
        top = 0
        for k in range(len(row)):
            left = row[k - 1] if k > 0 else 1
            right = row[k + 1] if k + 1 < len(row) else 1
            # Burst row[k] now, then do as well as possible with the rest
            coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
            top = max(top, coins)
        return top

    return burst_all(nums)

Рекурсия на последнем шарике с мемоизацией

Идея

Дополните ряд единицей с каждого конца: vals = [1] + nums + [1]. Заглушки никогда не лопаются и заменяют отсутствующих соседей. Пусть solve(left, right) — максимальное количество монет, которое можно получить с шаров строго между двумя оставшимися позициями.

Пусть k — шар, который лопается последним в этом промежутке. Все остальные шары в нём лопаются, пока k стоит как стена, поэтому в промежутке между left и k остаются только свои шары и две фиксированные границы, и то же самое верно для промежутка между k и right. Когда лопается k, его соседями оказываются именно left и right. Поэтому для промежутка лучший результат — это, для каждого k, лучший результат для двух частей плюс vals[left] × vals[k] × vals[right]. Ответ — результат для промежутка между двумя заглушками. Примерно n²/2 промежутков, в каждом из которых пробуются до n шаров, поэтому мемоизация даёт сложность O(n³).

Алгоритм

Создай vals как nums, добавив по 1 в начало и конец, и присвой m длину получившегося списка.
Создай таблицу m × m, заполненную значениями -1.
Напиши solve(left, right): возвращай 0, если right - left < 2, и сохранённое значение, если оно есть.
В противном случае попробуй каждое k строго между ними в качестве последнего шарика, оставь наибольшее значение solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] и сохрани его.
Верни solve(0, m-1).

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    memo = [[-1] * m for _ in range(m)]

    # Most coins from the balloons strictly between left and right
    def solve(left, right):
        if right - left < 2:
            return 0
        if memo[left][right] >= 0:
            return memo[left][right]
        top = 0
        for last in range(left + 1, right):
            # last bursts after every other balloon in the gap
            coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
            top = max(top, coins)
        memo[left][right] = top
        return top

    return solve(0, m - 1)

Заполните таблицу интервалов по ширине

Идея

Рекурсия рассматривает только более узкие промежутки, поэтому заполняйте ту же таблицу с помощью циклов — сначала узкие промежутки, затем широкие. Тогда значения best[left][k] и best[k][right] уже будут окончательными, когда понадобятся для более широкого промежутка.

Для [2, 4, 3], дополненного до [1, 2, 4, 3, 1], best[0][4] проверяет каждый шарик как последний. Если последним лопнуть шарик 3, получится best[0][3] = 30 плюс 1 × 3 × 1, итого 33 — лучший результат из трёх.

Объём работы такой же, как в версии с мемоизацией, но обычные циклы позволяют пропустить миллионы вызовов функций, благодаря чему эта версия работает в несколько раз быстрее в таких языках, как Python или R.

Алгоритм

Создай vals как nums, добавив по 1 с каждого конца, и установи m равным его длине.
Создай таблицу m × m best, заполненную нулями.
Для каждой ширины от 2 до m-1 и каждого left, для которого right = left + width находится внутри массива, перебери все значения k, строго расположенные между ними.
Установи best[left][right] равным наибольшему значению из best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right].
Верни best[0][m-1].

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    # best[left][right]: most coins from the balloons strictly between left and right
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            edge = vals[left] * vals[right]
            top = 0
            for last in range(left + 1, right):
                # last goes after every other balloon in the gap,
                # so left and right are its neighbours when it bursts
                coins = best[left][last] + best[last][right] + edge * vals[last]
                if coins > top:
                    top = coins
            best[left][right] = top
    return best[0][m - 1]

Ловушки и крайние случаи

Разделение при первом лопании с исходными соседями: nums[k-1] × nums[k] × nums[k+1] плюс два края. Этих соседей уже может не быть: для [2, 4, 3] такой подход выдаёт 44 — больше, чем можно получить при любом реальном порядке.
Заполнение таблицы построчно с увеличением left. Тогда best[k][right] для k > left ещё не вычислено, и его значение равно 0. Заполняйте таблицу по ширине или перебирайте left в убывающем порядке.
Пометка нерешённого промежутка в мемоизации значением 0. Промежуток с шарами, значения которых равны нулю, действительно даёт 0, поэтому при каждом посещении он решается заново. Используйте -1.
В Lua и R дополненные позиции нумеруются от 1 до m, поэтому ответ — best[1][m].

Частые вопросы3

Почему в задаче Burst Balloons выбирают последний шарик, а не первый?

После первого взрыва его две стороны становятся соседними, поэтому они по-прежнему влияют друг на друга. Последний шар в отрезке остаётся, пока остальные лопаются, поэтому его две стороны никогда не встречаются, и каждая из них представляет собой независимую подзадачу. Когда он лопается, его соседями становятся границы отрезка.

Какова временная сложность задачи «Взрывающиеся шарики»?

Время O(n³) и память O(n²): около n²/2 промежутков, в каждом из которых пробуем до n шаров в качестве последнего. Для 300 шаров это около 4.5 × 10^6 шагов. Перебор всех порядков — O(n · n!).

Можно ли решить задачу «Лопнуть шарики» с помощью жадного порядка?

Нет. Если первым лопнуть самый маленький шарик, получится 24 для [2, 4, 3], хотя можно получить 33. Если лопнуть тот, который сейчас приносит больше всего, получится 42 для [2, 9, 2], хотя если первым лопнуть шарик со значением 2, получится 18 + 18 + 9 = 45. Каждый лопнувший шарик меняет цены на последующие.

def maxCoins(nums):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

nums = [2, 4, 3]

Ожидаемый вывод

Burst Balloons

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуйте все порядки взрывания

Рекурсия на последнем шарике с мемоизацией

Заполните таблицу интервалов по ширине

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи