Dynamic programming bursting balloons(sylhare.github.io)
sylhare.github.io
Dynamic programming bursting balloons
https://sylhare.github.io/2025/07/29/bursting-balloons.html
7 comments
Am I completely misunderstanding the problem, or is the math in the example solution wrong?
The first error seems to be a transcription error, it's correct in their graph representation further down.
The second one isn't an error, but a poor explanation. After a balloon is burst, the balloons now have new neighbors. That is, it isn't this:
The second one isn't an error, but a poor explanation. After a balloon is burst, the balloons now have new neighbors. That is, it isn't this:
3 1 5 -> pop 1 = 15
3 _ 5 -> pop 3 = 3
3 1 5 -> pop 1 = 15
3 5 -> pop 3 = 15
If you have "3 1 5" and you burst 1, you gain 3x1x5 points and the state becomes "3 5", with the two remaining balloons being adjacent to each other.
The "1x3x1=1" part for the earlier example is a typo indeed, it should be 3.
The "1x3x1=1" part for the earlier example is a typo indeed, it should be 3.
This is fairly old Leetcode problem (who probably got it from somewhere else)
https://leetcode.com/problems/burst-balloons/description/
Its tricky and if I got this problem in a tech interview, I would be hard-pressed to solve it in 45 minutes if I hadn't seen it before
https://leetcode.com/problems/burst-balloons/description/
Its tricky and if I got this problem in a tech interview, I would be hard-pressed to solve it in 45 minutes if I hadn't seen it before
yeah, i would expect a candidate who hasn’t seen it before to have at best a 50/50 shot of realizing that the traversal is “in reverse” so to speak, and need a hint to move forward.
though once you know that i’d expect a candidate to bang it out fairly quickly. it’s not that many lines of code.
though once you know that i’d expect a candidate to bang it out fairly quickly. it’s not that many lines of code.
this would really be helped by demonstrating the wrong way to solve this, which is trying to think of the first balloon in the range and then combine with the subproblems. i expect this to be where people who know about dp are most likely to get hung up, and may not realize they can think about it the opposite way.
That’s exactly what I tried lol