Paint
Contest: Codeforces Round 743 (Div. 1)
Difficulty rating: 2700
Tags: dp, greedy

You are given a $$$1$$$ by $$$n$$$ pixel image. The $$$i$$$-th pixel of the image has color $$$a_i$$$. For each color, the number of pixels of that color is at most $$$20$$$.

You can perform the following operation, which works like the bucket tool in paint programs, on this image:

- pick a color — an integer from $$$1$$$ to $$$n$$$;
- choose a pixel in the image;
- for all pixels connected to the selected pixel, change their colors to the selected color (two pixels of the same color are considered connected if all the pixels between them have the same color as those two pixels).

Compute the minimum number of operations needed to make all the pixels in the image have the same color.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$).

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3\cdot10^3$$$) — the number of pixels in the image.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the colors of the pixels in the image.

Note: for each color, the number of pixels of that color is at most $$$20$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot10^3$$$.

Output format:
For each test case, print one integer: the minimum number of operations needed to make all the pixels in the image have the same color.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the optimal solution is to apply the operation on the third pixel changing its color to $$$2$$$ and then to apply the operation on any pixel that has color $$$2$$$ changing its color and the color of all pixels connected to it to $$$1$$$. The sequence of operations is then: $$$[1, 2, 3, 2, 1] \to [1, 2, 2, 2, 1] \to [1, 1, 1, 1, 1]$$$.

In the second example, we can either change the $$$1$$$s to $$$2$$$s in one operation or change the $$$2$$$s to $$$1$$$s also in one operation.

In the third example, one possible way to make all the pixels have the same color is to apply the operation on the first, third and the fourth pixel each time changing its color to $$$2$$$.

Example input:
3
5
1 2 3 2 1
4
1 1 2 2
5
1 2 1 4 2

Example output:
2
1
3

Editorial:
Firstly, we can notice that when we modify a segment of the form $$$[a, b, a]$$$ and change it to $$$[a, a, a]$$$ by performing the operation on the second element, as opposed to performing the operation first on the third element and then on the second element (like so $$$[a, b, a] \to [a, b, b] \to [a, a, a]$$$) we avoid using one unnecessary operation. In our solution we will try to maximize the number of operations that we didn't have to perform.
Let $$$dp[i][j]$$$ be the maximum number of operations that we can avoid on the interval from $$$i$$$ to $$$j$$$, while making all of its elements have the same color. Then the answer to the problem will be $$$n-1-dp[1][n]$$$. For $$$i \ge j$$$ we have $$$dp[i][j] = 0$$$ and for $$$i < j$$$ $$$dp[i][j]$$$ will be the maximum of $$$dp[i + 1][j]$$$ and $$$\max(1 + dp[i + 1][k - 1] + dp[k][j])$$$ over $$$i< k\le j$$$ such that $$$a[i]=a[k]$$$. It's because we can either not save any operations on the $$$i$$$-th element and just take the answer from the interval $$$[i + 1, j]$$$ or we can save one operation while coloring the segment from $$$i$$$ to $$$k$$$ and take the answer from segments $$$[i+1, k-1]$$$ and $$$[k, j]$$$. Because each color occurs in $$$a$$$ at most $$$20$$$ times, we can calculate this $$$dp$$$ in $$$O(20n^2)$$$ which is also our final time complexity.