Dynamic Programming21 sections · 916 units
Open in Course

Lessons from Burst Balloons

summary

Burst Balloons shows that sometimes you need to think backwards. "Which first?" creates dependencies. "Which last?" often simplifies them. The open interval trick (dp[i][j]dp[i][j] for strictly between) is common when boundaries interact with the answer.

When picking the locally best option fails and choices affect future options, consider interval DP with reverse thinking. Take time to work through examples.