Dynamic Programming • Interval DP

Burst Balloons

Maximize coins collected by bursting balloons. Bursting a balloon multiplies its value with its adjacent unburst balloons.

Try Interactive Simulator

Overview

Bursting a balloon changes the adjacent balloons for its neighbors. This means subproblems overlap and interfere if we process them in the normal forward direction.

Reverse Thinking

Instead of guessing which balloon to burst first, we guess which balloon is burst LAST in an interval [i, j].

State Independence

If balloon k is burst last, then the subproblems [i, k-1] and [k+1, j] are completely independent, allowing us to use DP.

Key Insight

The balloon burst last in interval [i, j] will be adjacent to the boundaries i-1 and j+1. Its coin yield is `nums[i-1] * nums[k] * nums[j+1]`.

1(pad)

3

1

5

8

1(pad)

Code Tracker

:::

1let nums = [1, ...rawNums, 1];

2for (let len = 1; len <= N; len++) {

3 for (let i = 1; i <= N - len + 1; i++) {

4 let j = i + len - 1;

5 for (let k = i; k <= j; k++) {

6 dp[i][j] = Math.max(

7 dp[i][j],

8 dp[i][k-1] + nums[i-1]*nums[k]*nums[j+1] + dp[k+1][j]

9 );

10 }

11 }

12}