Dynamic programming bursting balloons | Hacker News Reader

Dynamic programming bursting balloons

sylhare.github.io

16 pointsingve7 comments

Am I completely misunderstanding the problem, or is the math in the example solution wrong?

    Bursting 1 first gives you 3×1×5=15 coins. <-- OK...
    Bursting 3 first gives you 1×3×1=1 coins. (using left virtual balloon) <-- Should be 3?
    A possibility would be bursting 1, then 5, then 3, which gives you a total of 3×1×5+3×5×1+1×3×1=33 coins. <-- Should be 3x1x5+1x5x1+1x3x1=24?

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 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:

  3 1 5 -> pop 1 = 15
  3 _ 5 -> pop 3 = 3

It's:

  3 1 5 -> pop 1 = 15
  3 5   -> pop 3 = 15

The distance between the balloons doesn't make them not neighbors.

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

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.

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

Reply on news.ycombinator.com