Burst Balloons
Signals to notice
Brute force first
Try every order of balloon bursting. Factorial because each burst changes what's adjacent. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Interval DP: think of adding balloons instead of removing them. dp[i][j] = max coins from bursting all balloons between i and j (exclusive). For each possible last balloon k in (i,j), dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]). Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
What must stay true
By thinking of k as the LAST balloon burst in the interval (i,j), the left and right subproblems become independent — the boundaries i and j are guaranteed to still exist when k is burst. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Easy way to go wrong
Thinking about which balloon to burst FIRST — that makes subproblems dependent. Reversing the perspective to 'which is burst LAST' is the key insight that makes intervals independent. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.