Burst Balloons

+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 — соседи, поэтому за лопание 2 вы получите 1 × 2 × 3 = 6, а 3, оставшаяся одна, принесёт 1 × 3 × 1 = 3. Итого получается 33, и ни один другой порядок не даст больше: если сначала лопнуть маленькую 2, вы уже ограничите результат 24.

+15 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Выбери любой шарик, чтобы лопнуть его сейчас, собери left × value × right с его текущими соседями, убери его из ряда и реши укороченный ряд тем же способом. Проделай это для каждого варианта и оставь наибольшую сумму. Рекурсивная функция burstAll(row) делает именно это. Она перебирает все возможные порядки, поэтому ответ верный.

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

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

Алгоритм

Напиши burstAll(row), которая возвращает максимальное количество монет, полученных из шаров в row.
Для каждой позиции k считай соседние значения, используя 1 за каждым из концов.
Получи left × row[k] × right и прибавь результат вызова burstAll для строки без row[k].
Верни максимальную сумму для всех k или 0, если строка пуста.
Вызови 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)

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

Идея

Сначала поставь 1 с обоих концов: vals = [1] + nums + [1]. Эти два шарика никогда не лопаются и обозначают отсутствующих соседей по краям. Теперь рассмотрим промежуток между двумя позициями left и right, которые всё ещё стоят, и зададимся вопросом: какой шарик внутри промежутка лопнет последним?

Пусть это будет k. Пока остальные шарики в промежутке лопаются, k остаётся на месте, стоя между ними, словно стена. У каждого шарика между left и k соседи только из этого участка, а left и k служат неподвижными границами; то же самое верно для участка между k и right. Значит, эти два участка — независимые задачи того же типа. Когда k наконец лопается, между границами уже ничего не остаётся, поэтому его соседями оказываются именно left и right, а за него начисляется vals[left] × vals[k] × vals[right]. Если выбрать первый шарик, такого разделения не получится, потому что его стороны станут соседями.

Получаем рекурсию. solve(left, right) возвращает максимальное количество монет, которое можно получить за шарики строго между left и right: 0, если промежуток пуст, иначе — наибольшее значение solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] для каждого k в промежутке. Ответ — solve(0, m-1), то есть промежуток между двумя упорами.

Без дополнительных мер рекурсия снова и снова обрабатывает один и тот же промежуток, поэтому сохраняй каждый результат в таблице memo[left][right] и возвращай его при следующем обращении. Промежутков примерно n²/2, и для каждого проверяется до n шариков, поэтому объём работы составляет O(n³). Для ещё не решённого промежутка используй -1, потому что 0 — это реальный ответ. Рекурсия никогда не углубляется больше чем на n+1 вызовов, поскольку каждый вызов работает с более узким промежутком.

Алгоритм

Создай 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][right] — максимальное количество монет, которое можно получить за шарики строго между left и right; для пустого промежутка это 0. Для каждой ширины, начиная с 2, и каждого промежутка этой ширины попробуй каждый k внутри в качестве последнего шарика. best[left][k] и best[k][right] соответствуют более узким промежуткам, поэтому их значения уже окончательные.

Возьмём [2, 4, 3]. После дополнения получаем vals = [1, 2, 4, 3, 1] в позициях от 0 до 4, а ответ — это best[0][4]. Заполняем промежутки, начиная с самых узких:

Ширина 2, внутри один шарик: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], шарики 2 и 4: если последним будет 2, получим 0 + 24 + 1 × 2 × 3 = 30; если последним будет 4, получим 8 + 0 + 1 × 4 × 3 = 20. Значит, 30.
best[1][4], шарики 4 и 3: если последним будет 4, получим 0 + 12 + 2 × 4 × 1 = 20; если последним будет 3, получим 24 + 0 + 2 × 3 × 1 = 30. Значит, 30.
best[0][4], все три шарика: если последним будет 2, получим 0 + 30 + 1 × 2 × 1 = 32; если последним будет 4, получим 8 + 12 + 1 × 4 × 1 = 24; если последним будет 3, получим 30 + 0 + 1 × 3 × 1 = 33. Значит, 33.

Восстанови порядок по выбранным вариантам: последним идёт 3, перед ним последним на отрезке слева от него идёт 2, а 4 идёт первым. Получаем 24 + 6 + 3 = 33.

Вычислительная работа такая же, как и при использовании мемоизации: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 шагов для 300 шариков и таблица из 302 × 302 чисел. Обычные циклы позволяют избежать миллионов вызовов функций, поэтому эта версия в несколько раз быстрее рекурсии в таком языке, как Python или R.

Алгоритм

Создай vals из nums, добавив по одной единице с каждого конца, и установи 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]

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

Обычные ошибки — это жадный порядок, рекурсия по первому лопнувшему шарику, неверный маркер в мемоизации и заполнение таблицы в неправильном порядке.

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

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

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

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

Какова временная сложность задачи Burst Balloons?

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

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

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

Зачем добавлять 1 в начале и в конце массива?

Отсутствующий сосед считается равным 1, поэтому два шарика-подкладки со значением 1, которые никогда не лопаются, дают каждому настоящему шарику двух соседей без особых случаев. Они также служат границами всей задачи: ответ — это разрыв между двумя подкладками, best[0][m-1].

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [2, 4, 3]

Ожидается

Burst Balloons

Функция

Ограничения

Примеры

Подсказки

Решение

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

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

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

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

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

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