# dynamic programming – Count minimum number of steps to destroy all blocks Given a sequence of integers $$A_x$$ of length $$n$$ such that $$1 leq A_x leq N$$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the same value as the element we remove. We want to count the minimum number of steps to remove all elements.

For example, if our sequence is $$[1, 2, 2, 2, 2, 3, 3, 3, 1]$$, we can remove it in three steps: firstly we remove the twos, then we remove the threes, and on the end we remove the final two ones.
Our sequence transforms as follow: $$[1, 2, 2, 2, 2, 3, 3, 3, 1] to [1, 3, 3, 3, 1] to [1, 1]$$.

I tried using Dynamic Programming to solve this problem, and my idea was to use $$DP[i][j]$$ to represent the minimum steps to clear the interval $$[i, j]$$, however I’m not sure how to work out the transitions, and I’m stuck on the part that there can be some element in the middle of the interval which can be merge with the ends of the interval, and my DP relations cannot handle such cases. Posted on Categories Articles