Official Analysis (C++)

Solution

Explanation

In line with the spirit of range DP, let's define $dp[i][j]$ as the minimum number of swipes it takes to clear all the gems between indices $i$ and $j$ inclusive. If $i > j$ then there's no gems in the range and the array will return $0$.

There's two situations we can transition from.

The first is comparatively simpler, and it's where we erase either the first or first two elements from the array (if they're equal). In this case, the value we get is $dp[i+1][j]+1$ or $dp[i+2][j]+1$.

The second case is a bit nastier, and it may seem a bit unintuitive at first:

If $i + 2 \le k \le j$ and the gems at positions $i$ and $k$ are the same color, then we can update with the following candidate value:

$$dp[i+1][k-1]+dp[k+1][j]$$

You may wonder why there's no extra swipe involved in this transition. After all, where did we clear gems $i$ and $k$?

The answer is that we can clear them along with the last swipe that erased what was left in $dp[i+1][k-1]$. Since the last swipe that cleared these gems was a palindrome, we can take on $i$ and $k$ to the start and end without any problems.

Implementation

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

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

public class Zuma {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int gemNum = Integer.parseInt(read.readLine());
		int[] gems = Arrays.stream(read.readLine().split(" "))
		                 .mapToInt(Integer::parseInt)
		                 .toArray();