Question on given example


  • 0
    N

    In the example it says:

     nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
    

    But I am wondering why it doesn't pick 5*8*1 in the first iteration?


  • 1
    T

    If you pick 5*8*1 in the first iteration, you must burst the 8 balloon. This gives you a sum of 40 so far.

    Without the 8 balloon available, you can only add 3, 15, or 5 coins on the next iteration.

    The following bursts can't get you very close to the optimal answer if you start with 8.

    More uses of the 8 balloon as an adjacent balloon will get you a higher answer, which is not possible if you burst 8 first.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.