[HN Gopher] Dynamic programming bursting balloons
       ___________________________________________________________________
        
       Dynamic programming bursting balloons
        
       Author : ingve
       Score  : 7 points
       Date   : 2025-07-30 18:39 UTC (2 days ago)
        
 (HTM) web link (sylhare.github.io)
 (TXT) w3m dump (sylhare.github.io)
        
       | jasonpeacock wrote:
       | Am I completely misunderstanding the problem, or is the math in
       | the example solution wrong?                   Bursting 1 first
       | gives you 3x1x5=15 coins. <-- OK...         Bursting 3 first
       | gives you 1x3x1=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 3x1x5+3x5x1+1x3x1=33 coins. <-- Should
       | be 3x1x5+1x5x1+1x3x1=24?
        
         | mauricioc wrote:
         | 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.
        
         | Jtsummers wrote:
         | 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.
        
       | SJC_Hacker wrote:
       | 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
        
       ___________________________________________________________________
       (page generated 2025-08-01 23:01 UTC)