LeetCode 312 Burst Balloons - Transition

For $dp[i][j]$, try each balloon $k$ in $(i,j)$ as the last one to burst. Coins = $dp[i][k]$ + $dp[k][j]$ + $nums[i] \times nums[k] \times nums[j]$.

The first two terms are coins from clearing the left and right. The last term is from bursting k when only i and j remain as neighbors. $dp[i][j]$ = max over all $k$ in $(i,j)$ of this expression. The formula tells you how to compute dp[i][j] from smaller ranges. Getting this right is the core of DP.