Burst Balloons — Interval DP

Problem

Array of balloons. Bursting balloon i gives nums[i-1]*nums[i]*nums[i+1]. Maximize total coins.

Key Insight — Last Balloon in Interval

Instead of thinking which to burst first (hard), think which to burst last in interval [i,j]. The last balloon k is surrounded by i-1 and j+1 (already burst).

dp[i][j] = max over k: dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]

Time: O(n³) | Space: O(n²)

Solutions

Python

class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        nums=[1]+nums+[1]; n=len(nums)
        dp=[[0]*n for _ in range(n)]
        for length in range(2,n):
            for i in range(0,n-length):
                j=i+length
                for k in range(i+1,j):
                    dp[i][j]=max(dp[i][j], dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j])
        return dp[0][n-1]

C++

class Solution {
public:
    int maxCoins(vector<int>& nums){
        nums.insert(nums.begin(),1); nums.push_back(1);
        int n=nums.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        for(int len=2;len<n;len++)
            for(int i=0;i<n-len;i++){
                int j=i+len;
                for(int k=i+1;k<j;k++)
                    dp[i][j]=max(dp[i][j],dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j]);
            }
        return dp[0][n-1];
    }
};

Complexity

Time: O(n³) | Space: O(n²)