Minimum Time to Make Rope Colorful
Last updated
Last updated
There is are approaches that uses or greedy instead but I will not cover those.
Consecutive balloons do not count the popped balloons, so popping the middle R
in RRR
will still violate the criteria of having no consecutive colors.
Let's start with an arbitrary rope with balloons: RRRGGBB
and an arbitrary cost of [2, 1, 5, 3, 4, 1, 2]
. From hand-simulation, we know that the ultimate "optimal" answer is XXRXGBX
where X
are the popped balloons.
For every segment of like colors, we never pop the highest cost balloon to achieve the lowest possible cost within the segment (the mathematical proof is relatively easy to come up with)
When encountering a same color, a decision between popping the current balloon or the previously seen, unpopped, same balloon should be made, with the decision made to be the smallest of the two (see (1))
For every segment of same color, once a balloon encountered is of a different color, there's no need to pop anymore of the previous color so the color tracked can be changed
prev
is needed alongside the recurrence.
Processing from left to right, can be interpreted as the minimum time to make the rope colorful. This means we are solving for the prefix of the array.
If is the same as the previous color, we need to make the decision to pop based on observation (1) using the minimum between the current cost to pop and the cost to pop the previous same color balloon.
If is not the same, then we simply need to update the "previous color" and we know that since there is no balloons to pop.
We will apply the state caching optimization, where , only storing the previous time to make the rope colorful as .