Official Analysis (C++)

Explanation

Without regards for actual correctness, let's just set up what seems like an intuitive DP state. Let's have $\texttt{min\_ops}[s][e]$ be the minimum number of operations it takes to make all the numbers from $s$ to $e$ inclusive the same. For transitions, we can come from either $\texttt{min\_ops}[s][e-1]$ or $\texttt{min\_ops}[s+1][e]$. There's also a change that the numbers at $s$ and $e$ are the same, in which case we can transition from $\texttt{min\_ops}[s+1][e-1]$.

The problem with this setup, is that it's, well, wrong. However, we can make it right with some observations into why it outputs the wrong answer. Take the first sample case:

5 2 2 1

$\texttt{min\_ops}[1][2]$ should equal $0$, but our transitions set it to be $1$. The reason it does this is that our algorithm fails to detects elements that are already the same and don't need to be merged any further. This phenomenon can be observed more clearly if you plug in, say, 10 numbers, all of which are the same.

A key observation to combat this is that we can treat ranges of consecutive identical numbers as just a single number. This way, we can guarantee that each element is different from its neighbors, and that no pre-connected components exist.

After this step of preprocessing, our DP definition is now valid.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
	int len;

Copy
import java.io.*;
import java.util.*;

public class FloodFill {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int len = Integer.parseInt(read.readLine());
		List<Integer> arr = new ArrayList<>();
		StringTokenizer arrST = new StringTokenizer(read.readLine());
		for (int i = 0; i < len; i++) {

Copy
from itertools import groupby

len_ = int(input())
arr = [int(i) for i in input().split()]
arr = [v for v, _ in groupby(arr)]
len_ = len(arr)

min_ops = [[0 for _ in range(len_)] for _ in range(len_)]
for l in range(2, len_ + 1):
	for start in range(len_ - l + 1):