Example: Burst Balloon Problem - rFronteddu/general_wiki GitHub Wiki

You are given an array of balloons. You must determine how to crush them to maximize profit.

ex. 3, 1, 5, 8

• If I crash 1, 3, 8, 8 => 1x3x5 (when there is no left mul by 1) + 1x3x5 (1 was crushed so 5 is to the right of 3 now) + 1x5x8 + 1x8x1

• len = 1 => there is only one balloon, for d[0,0] first element is the profit left x curr x right, second is the last exploded balloon

---	0	1	2	3
0	3,0
1		15,1
2			40,2
3				40,3

ex. 3, 1, 5, 8

• len = 2 => we need to find the best split
  • consider 0,1
    • if k == 0 (last to explode) => 0 + d[1,1] + 1x3x5 = 15 + 15
    • if k == 1 (last to explode) => d[0,0] + 1x1x5 + 0 = 3 + 5

---	0	1	2	3
0	3,0	30,0	159,0	167,3
1		15,1	135,2	159,3
2			40,2	48,3
3				40,3

ex. 3, 1, 5, 8

• len = 3 => we need to find the best split
  • consider 0,2
    • if k == 0 => 0 + d[1,2] + 1x3x8 = 159 (note that 1..2 exploded so left of 0 is now 3)
    • if k == 1 => d[0,0] + 1x1x8 + d[2,2] = 3 + + 40
    • if k == 2 => d[0,1] + 1x5x8 + 0 = 70

balloon(x)
    n = x.len
    d[0..n-1, 0,..n-1]

    // Initialize the base cases
    for i = 0 to n-1:
        left = if i == 0 then 1 else x[i-1]
        right = if i == n-1 then 1 else x[i+1]
        d[i,i] = (left * x[i] * right, i)

    for len = 2 to n
        for i = 0 to n-l
            j = i+l-1
            // find best split
            d[i,j] = (0,-1)
            for k = i to j
                left = k == i ? 0 : d[i, k-1][0]
                right = k == j ? 0 : d[k+1, j][0]
                
                a = i == 0 ? 1 : x[i-1]
                b = j == n-1 ? 1 : x[j+1]
                q = left + right + a*b*x[k]
                if q > d[i,j][0]
                    d[i,j] = (q, k)

    print("Max value is :" + d[0,n-1][0])
    print("Last balloon is: " + d[0,n-1][1])
    printBurstSequence(d, x, 0, n-1)

printBurstSequence(d, x, i, j)
    if i > j 
        return
    k = d[i,j][1]
    print("Burst Balloon at index: " + k)
    printBurstSequence(d, x, i, k-1)  
    printBurstSequence(d, x, k+1, j)