Burst Balloons is one of the most famous Interval DP problems.

You are given:

nums[] 

Goal:

Maximize coins obtained by bursting all balloons.

Coins gained:

nums[left] * nums[current] * nums[right] 

Example

nums = [3,1,5,8] 

Output:

167 

Key Observation

Instead of asking:

Which balloon to burst first? 

Think:

Which balloon to burst last? 

This converts the problem into Interval DP.

DP State

dp[i][j] = Maximum coins obtainable from interval i to j

Choose balloon k as last burst:

dp[i][j] = max(dp[i][k-1] + nums[i-1] * nums[k] *nums[j+1] + dp[k+1][j])

Dry Run

Input:

[3,1,5,8] 

Modified:

[1,3,1,5,8,1] 

Best Order:

1
↓
5
↓
3
↓
8 

Answer:

 167

Approach 1 : Memoization

Explanation

For every interval:

1. Choose last balloon.
2. Solve left interval.
3. Solve right interval.
4. Add current gain.
5. Store answer.

Approach 2 : Tabulation

Explanation

State:

 dp[i][j]

Meaning:

Maximum coins inside interval. 

Transition:

Try every k as last balloon.

Practice

def maxCoins(nums):

    nums = [1] + nums + [1]

    n = len(nums)

    dp = [[0] * n for _ in range(n)]

    for length in range(1, n - 1):

        for i in range(1, n - length):

            j = i + length - 1

            for k in range(i, j + 1):

                dp[i][j] = max(dp[i][j], dp[i][k - 1] + nums[i - 1] * nums[k] * nums[j + 1] + dp[k + 1][j])

    return dp[1][n - 2]


print(maxCoins([3, 1, 5, 8]))