Problem modification: what if the balloons are in circular order


  • 0
    A

    I think that a possible modification is that if the balloons are in a circle.

    When only two balloons are left the coins given on bursting first balloon would be product of two numbers. When only one balloon is left it would be number itself.

    We can solve this by again considering every element one by one as the last burst, then converting the circle into a array bounded by the last burst element. We can then solve the array by DP as earlier.

    eg. 5,10,2,20,45 are in circle then we need to solve the below set and find the maximum

    5[10,2,20,45]5 + 5
    10[2,20,45,5]10 + 10
    2[20,45,5,10]2 + 2
    20[45,5,10,2]20 + 20
    45[5,10,2,20]45 + 45

    However, complexity will be O(N^4). Is there a better method to solve this.
    One way is to find all local minimums and burst the least among them, since I think a circular arrangement is bound to have at least one minimum. We can keep doing this iteratively to get O(N^2) complexity. I am not sure though if that will work. Any suggestions are welcome.


Log in to reply
 

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