Flood Fill
Contest: Codeforces Round 538 (Div. 2)
Difficulty rating: 1900
Tags: dp

You are given a line of $$$n$$$ colored squares in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. The $$$i$$$-th square initially has the color $$$c_i$$$.

Let's say, that two squares $$$i$$$ and $$$j$$$ belong to the same connected component if $$$c_i = c_j$$$, and $$$c_i = c_k$$$ for all $$$k$$$ satisfying $$$i < k < j$$$. In other words, all squares on the segment from $$$i$$$ to $$$j$$$ should have the same color.

For example, the line $$$[3, 3, 3]$$$ has $$$1$$$ connected component, while the line $$$[5, 2, 4, 4]$$$ has $$$3$$$ connected components.

The game "flood fill" is played on the given line as follows:

- At the start of the game you pick any starting square (this is not counted as a turn).
- Then, in each game turn, change the color of the connected component containing the starting square to any other color.

Find the minimum number of turns needed for the entire line to be changed into a single color.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of squares.

The second line contains integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 5000$$$) — the initial colors of the squares.

Output format:
Print a single integer — the minimum number of the turns needed.

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

Note:
In the first example, a possible way to achieve an optimal answer is to pick square with index $$$2$$$ as the starting square and then play as follows:

- $$$[5, 2, 2, 1]$$$
- $$$[5, 5, 5, 1]$$$
- $$$[1, 1, 1, 1]$$$

In the second example, a possible way to achieve an optimal answer is to pick square with index $$$5$$$ as the starting square and then perform recoloring into colors $$$2, 3, 5, 4$$$ in that order.

In the third example, the line already consists of one color only.

Example input:
4
5 2 2 1

Example output:
2

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

Example output:
4

Editorial:
This problem was inspired by the game Flood-it. It is apparently NP-hard. You can try out the game here. https://www.chiark.greenend.org.uk/%7Esgtatham/puzzles/js/flood.html
The first solution is rather straightforward. Suppose squares $$$[L, R]$$$ are flooded, then they are either of color $$$c_L$$$ or $$$c_R$$$. We can define $$$dp \left( L, R, dir \right)$$$ as the minimum number of moves required to make the segment $$$[L, R]$$$ monochromic:
• $$$dp \left( L, R, 0 \right)$$$ is the least moves required to make the segment having color $$$c_L$$$.
• $$$dp \left( L, R, 1 \right)$$$ is the least moves required to make the segment having color $$$c_R$$$.
The second solution, which is the author's intended solution is less so. Note that the size of the component doesn't matter, so first "compress" the array so that every adjacent elements are different. We will work on this compressed array instead.
We want to maximize the number of turns that we can fill two adjacent squares instead of one. From a starting square, this maximum number of "saved" turns is equal to the longest common subsequence (LCS) of the array expanding to the two sides. The answer is the $$$N$$$ - (maximum LCS over all starting squares)
This is equivalent to finding the longest odd size palindrome subsequence. In fact, it is the longest palindrome subsequence. For every even-sized palindrome subsequence, since adjacent elements are different, we can just insert an element in the middle and obtain a longer palindrome subsequence.
To find the longest palindrome subsequence, we can make a reversed copy of the array and find LCS of it with the original array.
Alternatively, we can also use the first solution on the compressed array, without needing the third parameter.
Time complexity: $$$\mathcal{O} \left( n^2 \right)$$$.