1. Recursion

Every recursion starts by breaking down the final answer into subproblems, so we'll start by trying to write the final answer recursively. The final answer is the score of popping all the balloons. Obviously, it comes from when we only have 1 balloon left and then we pop it. All we need to do now is figure out which balloon we should pop last. We'll call the index of the last balloon k.

We get this recursive-looking equation, although remember, it only applies to the very last balloon pop:

To make this look more like code, we'll take the maxCoins function to be this:

We can now write the equation as:

It turns out the above equation is not exactly the recursion in general, since we assumed we were on the last pop. But now we have an idea of what to do in general. Let's now consider an arbitrary $\tt i$ and $\tt j$.

To find the max number of coins we can get by popping balloons $\tt i$ through $\tt j$, we just want to figure out which balloon k we should pop last out of any of the balloons between $\tt i$ and $\tt j$.

The kth balloon will be next to balloon $\texttt{i-1}$ and $\texttt{j+1}$ when it's popped, since we're popping it last. This means we'll gain $\texttt{nums[i-1] * nums[k] * nums[j+1]}$ coins by popping it. At this point we'll already have the coins of popping all the other balloons $\tt i$ through $\texttt{k-1}$ and $\texttt{k+1}$ through $\tt j$ first. We can write this all down as a recursion, which always works:

2. Base case

The recursion keeps going until $\tt maxCoins$ has $\tt j$ to the left of $\tt i$, or $\texttt{j==i-1}$. This interval doesn't make sense, so we can just set maxCoins to 0 here. This is our base case.

3. Code

We'll code this up with DP to avoid doing redundant calls. Notice that $\texttt{maxCoins(i, j)}$ only depends on $\texttt{maxCoins}$ with a smaller number of balloons, since k splits the balloons up. So we can just compute $\texttt{maxCoins}$ for smaller-length intervals of $\tt i$ and $\tt j$ first, and larger-length intervals last.

We'll also add a dummy balloon with a score of 1 to the left and right, so we don't have to treat the balloons on the ends differently from the other balloons.

Time Complexity $O(n^3)$. We have two for loops, plus another inner for loop to find the max over k.

Space Complexity $O(n^2)$ for the maxCoins 2D array.