Problem - Zuma

You have $n$ gemstones in a row, each with a color. In one move, you remove any contiguous palindromic substring. Find the minimum moves to remove all gemstones.

Example: $[1, 2, 1, 3, 3]$ takes $2$ moves. Remove $[3, 3]$, leaving $[1, 2, 1]$. Then remove $[1, 2, 1]$. Greedy removal of the longest palindrome doesn't always give the optimal answer. You need interval DP to explore all possible removal sequences.