Задача: 312. Burst Balloons
Сложность: hard

Дано n воздушных шаров, пронумерованных от 0 до n - 1. Каждый шарик окрашен в число, представленное массивом nums. Вам нужно лопнуть все шарики.
Если вы лопаете шарик i, вы получите nums[i - 1] * nums[i] * nums[i + 1] монет. Если i - 1 или i + 1 выходит за границы массива, то считайте, что там находится шарик с числом 1.
Верните максимальное количество монет, которое можно собрать, лопая шарики с умом.

Пример:

Input: nums = [1,5]
Output: 10

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка данных
Добавьте по одному шару с числом 1 в начало и конец массива nums, чтобы упростить обработку граничных случаев. Определите функцию dp(left, right), которая будет возвращать максимальное количество монет, если лопнуть все шары на интервале [left, right] включительно.

2⃣Вычисление значений для всех интервалов
Для каждого интервала [left, right] и каждого индекса i в этом интервале: Вычислите максимальные монеты, которые можно получить, сначала лопая все шары кроме i, а затем лопая i. Обновите dp(left, right) максимальной суммой этих монет.

3⃣Возврат результата
Верните значение dp(1, n - 2), которое будет содержать максимальное количество монет, которое можно собрать, лопнув все шары с умом, исключая добавленные нами шары.

😎 Решение:

class Solution {
    function maxCoins($nums) {
        $n = count($nums);
        $newNums = array_merge([1], $nums, [1]);
        
        $dp = array_fill(0, $n + 2, array_fill(0, $n + 2, 0));
        
        for ($length = 2; $length < $n + 2; $length++) {
            for ($left = 0; $left < $n + 2 - $length; $left++) {
                $right = $left + $length;
                for ($i = $left + 1; $i < $right; $i++) {
                    $dp[$left][$right] = max($dp[$left][$right],
                                             $newNums[$left] * $newNums[$i] * $newNums[$right] + $dp[$left][$i] + $dp[$i][$right]);
                }
            }
        }
        
        return $dp[0][$n + 1];
    }
}

Ставь 👍 и забирай 📚 Базу знаний