Specials

Burst Balloons - Reverse Trick

Problem: Bursting elements changes adjacency, breaking subproblem independence.

Idea: k is the last element to burst in [i, j], not the first.

• k acts as a solid wall while left and right subproblems are solved.
• Left subproblem [i, k] and right subproblem [k, j] become completely independent.
• When k finally bursts, its immediate neighbors are guaranteed to be the boundaries i and j (hence nums[i] and nums[j]).

Transition:

• Pad array with 1s on both ends.
• dp[i][j] = max coins bursting everything strictly between i and j.
• k = index of the last balloon to burst (i < k < j).
• merge_cost = nums[i] * nums[k] * nums[j]
• cost = dp[i][k] + dp[k][j] + merge_cost

The code is identical to rod cutting but the justification has changed.

Impl bias: k loops over the poppable balloons. i must start at 0 as i and j represent the unpoppable boundary walls.

Min cost to merge stones

The 2d dp is f(i,j) = min cost to merge to as small number of piles as possible and not necessarily k. We apply that k merge only when it’s possible so it’s really 2 transitions ( even in the 3d version - that’s just the nature of the problem )

Is len l mergeable to 1? l mod (k-1) == 1 is valid but not for k = 2, rather use (l-1) mod (k-1) == 0

f(i,j) = min cost to merge it - into whatever is this range megeable to which is deterministic and not somethng to optim

If the exit condition is true it IS one pile mergeable.

Transitions

• f(i,j) = f(i,k-1) + f(k,j) ⇒ min
• If it’s k reducible → merge it to 1 by adding cost

Remove boxes

I find this really really really hard to understand this one.

I’ve kind of understood the iterative version - which barely passes but is correct. The rec one allows for a cheap suffix compression which is quite faster apparently but I don’t think I should bother with that.