Count minimum number of steps to destroy all blocks

Question

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.

Answer 1

A very similar problem is the one of clearing the board in an instance of the Two-Dots that only has one column.

This is a single-player game played on a column of colored dots. A move consists of removing a contiguous group of at least two dots that all share the same color and then consolidating all remaining dots. The goal is to clear the column in the fewest number of moves.

A dynamic programming algorithm for this problem is devised in section 4.2.1 of this paper. As you suggest $C(i,j)$ is defined as the minimum number of moves needed to clear all (and only) the dots in rows $i$ through $j$.

Your problem has a couple of minor differneces:

1. A move always deletes a maximal (w.r.t. inclusion) monochromatic group of adjacent dots.
2. You can also remove a single "dot" if it doesn't match with any neighboring dot.

Here the constraint in 1) can be safely relaxed since it is the case that there is always an optimal solution for the Two-Dots problem that also satisfies such constraint.

To account for 2) you need to redefine $C(i,i) = 1$ (since a single dot can be removed with a single move) and and, for $i<j$, $C(i,j) = \min \{C_1(i,j), C_2(i,j), 1 + C(i+1,j) \}$ where $C_1$ and $C_2$ are as in the paper and $1 + C(i+1, j)$ considers the case where the first dot is not matched with anything in an optimal solution.