LeetCode 312 - Burst Balloons

Initially, I considered the problem in the forward direction. In particular, I considered if you popped an arbitrary balloon $i$, you now have two subproblems, namely the subproblem from $[1,i-1]$ and $[i+1, n]$ gives the solution to $x_i$.

This approach fails as the subproblems are not independent. For example while solving the [1,1] subproblem, we don't know how many balloons remain in the [3,5] subproblem. This is a problem as depending on which balloons are popped in the [3,5] subproblem, the score achieved by popping the single balloon in the [1,1] subproblem is different.

Generally when this happens, we should consider solving the problem backwards. The mental image in my head is trying to put a thread into a needle, vs pulling the thread out of the needle. In this case, we start the problem by going to the end of the problem, where all the balloons are popped. We then consider unpopping, or reviving each balloon. Instead of reversing the score, we still add to the score as each balloon is revived.

Notice how now, the [1,1] subproblem and the [3,5] subproblem are truely independent, as we know that balloon 2 exists. This way, when we revive the 1 balloon, we know that the score must be $1 * n_0 * n_1$ (switched to 0 indexing again 🙂), regardless of what happens in the [3,5] subproblem.

Implementation Details

We let $dp[i][j]$ to be the solution to the subproblem given all balloons $[0,i-1]$ and $[j+1,n)$ (namely $[0,n) \setminus [i,j]$) are already revived. In particular, we actually don't care if all of $[0,i-1)$ and $(j+1,n)$ are revived, as long as $i-1$ and $j+1$ are revived, the score only depends on the immediate neighbors of the range being revived.  I only force ALL the balloons to be revived because it is easier to think about the problem this way. I mention this because it is important to realize that we aren't only considering subproblems with contiguous outside ranges, and that's where most of the sparse cases are hiding.

I wrote a helper function nums_at(i) to return the score of the balloon at index $i$, or $1$ if $i$ is out of bounds. This makes it less annoying to write the code as otherwise I would need to put ternary conditions everywhere. Note that $n_i=nums\_at(i)$.

The trivial DP cases are $dp[i][i]$, where only one balloon needs to be revived. In this case, you revive the balloon and the score is the product of its score and its immediate neighbours' score. This corresponds to the code on lines 11, 12.

The DP transition is$$dp[i][j] = \max_{k \in [i,j]} \left( dp[i][k-1] + n_{i-1}n_kn_{j+1} + dp[k+1][j] \right)$$Namely, we visualize this as reviving the balloon at $k$, and solving the two independent subproblems, namely $[i,k-1]$ and $[k+1,j]$. This corresponds to lines 18 to 21 in the code.

Finally, we consider how to traverse the DP table. From the structure of the transitions are visualized below.

In particular, it is clear that we should fill from the diagonal up to the top right corner. In particular, we consider the following parameterization:

Namely, we have first iterate from $x\in [1, n)$, then iterate $y\in [0, n-x)$ and choose $(i,j)=(y,x+y)$. For those confortable with linear algebra, $$\begin{bmatrix} i\\j \end{bmatrix} = \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix} \begin{bmatrix} x\\y \end{bmatrix}$$ Namely, we construct a basis of vectors $\vec x_1=(0, 1)$ and $\vec x_2=(1, 1)$. The implementation follows this logic.