312. Burst Balloons

leetcode hard

#array#backtracking#csharp#dynamic-programming#hard#intervals#leetcode#math#two-pointers

Task

Дано 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

C# solution

matched/original

public class Solution {
    public int MaxCoins(int[] nums) {
        int n = nums.Length;
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        Array.Copy(nums, 0, newNums, 1, n);
        
        int[,] dp = new int[n + 2, n + 2];
        
        for (int length = 2; length < n + 2; length++) {
            for (int left = 0; left < n + 2 - length; left++) {
                int right = left + length;
                for (int i = left + 1; i < right; i++) {
                    dp[left, right] = Math.Max(dp[left, right],
                                               newNums[left] * newNums[i] * newNums[right] + dp[left, i] + dp[i, right]);
                }
            }
        }
        
        return dp[0, n + 1];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<int>& newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        Array.Copy(nums, 0, newNums, 1, n);
        
        int[,] dp = new int[n + 2, n + 2];
        
        for (int length = 2; length < n + 2; length++) {
            for (int left = 0; left < n + 2 - length; left++) {
                int right = left + length;
                for (int 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];
    }
}

Java solution

matched/original

public class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        System.arraycopy(nums, 0, newNums, 1, n);
        
        int[][] dp = new int[n + 2][n + 2];
        
        for (int length = 2; length < n + 2; length++) {
            for (int left = 0; left < n + 2 - length; left++) {
                int right = left + length;
                for (int i = left + 1; i < right; i++) {
                    dp[left][right] = Math.max(dp[left][right],
                                               newNums[left] * newNums[i] * newNums[right] + dp[left][i] + dp[i][right]);
                }
            }
        }
        
        return dp[0][n + 1];
    }
}

JavaScript solution

matched/original

var maxCoins = function(nums) {
    let n = nums.length;
    let newNums = [1, ...nums, 1];
    
    let dp = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0));
    
    for (let length = 2; length < n + 2; length++) {
        for (let left = 0; left < n + 2 - length; left++) {
            let right = left + length;
            for (let i = left + 1; i < right; i++) {
                dp[left][right] = Math.max(dp[left][right],
                                           newNums[left] * newNums[i] * newNums[right] + dp[left][i] + dp[i][right]);
            }
        }
    }
    
    return dp[0][n + 1];
};

Python solution

matched/original

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        n = len(nums)
        
        @lru_cache(None)
        def dp(left: int, right: int) -> int:
            if left > right:
                return 0
            max_coins = 0
            for i in range(left, right + 1):
                coins = dp(left, i - 1) + dp(i + 1, right) + nums[left - 1] * nums[i] * nums[right + 1]
                max_coins = max(max_coins, coins)
            return max_coins
        
        return dp(1, n - 2)

Go solution

matched/original

func maxCoins(nums []int) int {
    n := len(nums)
    newNums := make([]int, n+2)
    newNums[0] = 1
    newNums[n+1] = 1
    for i := 0; i < n; i++ {
        newNums[i+1] = nums[i]
    }
    
    dp := make([][]int, n+2)
    for i := range dp {
        dp[i] = make([]int, n+2)
    }
    
    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]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализация и подготовка данных

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

Вычисление значений для всех интервалов

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

Возврат результата

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

😎