Approach 1 — Brute Force

Generate all permutations in which to break the blocks. Simulate the chain reactions when they occur.

This is enough to obtain ~20\%~ of the points.

Time Complexity: ~\mathcal O(N! \times N)~

Approach 2 — Divide and Conquer

A faster solution uses memoization on a divide and conquer principle. The subproblem is determining the cost to knock down every pillar in the range ~[L, R]~ given whether pillar ~L-1~ is broken and whether pillar ~R+1~ is broken.

• In the base case, ~L = R~, and there is only 1 pillar to consider. The cost to knock it down is just its durability minus the possible damages done by the pillars to its left and right.
• Otherwise, if there is more than 1 pillar to consider:
  • If pillar ~L-1~ is broken and completely knocks over pillar ~L~ without you having to do any work, then we can narrow the range by 1 from the left and mark the newest left outside-border pillar as broken.
  • If pillar ~R+1~ is broken and completely knocks over pillar ~R~ without you having to do any work, then we can narrow the range by 1 from the right and mark the newest right outside-border pillar as broken.
  • Otherwise, we test every pillar between ~L~ and ~R~ as the first pillar to knock down, taking into account collateral damage. The total cost is the cost to break down this pillar, plus the cost to break all the pillars to the left of it, plus the cost to break all of the pillars to the right of it. In other words, we divide the range in half and let recursion handle each side. The minimum cost across all these tests is the answer.

If we cache the results every time we compute them, we only have ~\mathcal O(N^2)~ possible states to consider (all possible ~L~ values ~\times~ all possible ~R~ values). Each state requires ~\mathcal O(N)~ time to transition (trying to break down each pillar in the range). Overall, the solution is ~\mathcal O(N^3)~ and is given ~60\%~ of the points.

Time Complexity: ~\mathcal O(N^3)~

Approach 3 — Dynamic Programming

To get full marks, we abandon recursion altogether and go for pure dynamic programming. This problem displays optimal substructure in the following way. Consider the base case where we only want to break only the first (leftmost) block. Given this value, we can then use it to calculate the cost of breaking the two leftmost pillars. Likewise, if we know the cost to break the first ~i~ pillars, then we can calculate the cost to break the first ~i+1~ pillars.

There are 2 values in our state: the current pillar we are on, and whether it is broken (either ~0~ or ~1~). ~DP[i][\text{broken?}]~ stores the minimum cost to achieve this state. You can think of ~DP[][0]~ as the "important" values, since our goal is ultimately to knock pillars down. However, we will still need ~DP[][1]~ values to calculate the ~DP[][0]~ values along the way. Once again, ~DP[i][0]~ represents the cost to break all the pillars from ~1~ to ~i~. Every ~DP[i][0]~ state is equal to the minimum cost of two cases:

• the pillar before it is already knocked down (i.e. ~[i-1][0]~): Here, the additional cost to knock down one more pillar (the current one) is just the current pillar's durability ~D_i~, minus the damage done by the previous pillar ~W_{i-1}~.
• the pillar before it is not knocked down (i.e. ~[i-1][1]~): Here, there is no collateral damage at all, so the extra cost to break one more pillar (the current one) is just its durability ~D_i~.

Calculating ~DP[i][1]~ is slightly trickier. We must always assume that the pillar after it is broken. This is a valid assumption because in the next iteration, we always ensure that the assumption made in the previous iteration is fulfilled by actually assuming again that it is broken (i.e. ~[i+1][0]~). In other words, the assumptions in one iteration depend on the assumptions made in the next, and the assumption in the current iteration depends on the assumptions made in the previous. An interesting form of induction indeed. Yet again, we have 2 cases to consider, of which we take the minimum cost:

• the pillar before it is already knocked down (i.e. ~[i-1][0]~): Here, the additional cost to knock down one more pillar (the current one) is just the current pillar's durability ~D_i~, minus the damage done by the previous pillar ~W_{i-1}~, minus the damage done by the next pillar ~W_{i+1}~.
• the pillar before it is not knocked down (i.e. ~[i-1][1]~): Here, there is no collateral damage at all from the previous pillar, so the extra cost to break one more pillar (the current one) is just its durability ~D_i~ minus the damage done by the next pillar ~W_{i+1}~.

Time Complexity: ~\mathcal O(N)~