Interval DP

Opening scenario

Problem references use LC for LeetCode.

nums balloons sit in a row. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins, treating out-of-range as 1. The burst balloon is removed and its neighbors become adjacent. Maximize total coins (LC 312, Burst Balloons). Then the interviewer moves to a string. Partition it into palindromes: return the fewest cuts that leave every piece a palindrome. Or run the strange printer: each pass prints one contiguous block of the same character on top of what is already there. Return the fewest passes that build the string.

Balloon values are non-negative, and each burst uses the balloon’s current surviving neighbors. For the printer, a pass may overwrite earlier characters; the final string must match the target exactly. Begin by asking which choice would leave fixed boundaries around smaller subproblems.

Question progression

Q1 — Why does "which balloon to burst first" lead nowhere, and what's the state?

Question: You try dp[i][j] = max coins from…