hardDynamic Programming 2DPure DSA~40 min
Minimum Moves to Clear an Array by Palindrome Removal
A log compactor removes contiguous palindromic runs of event codes in a single operation. Each operation deletes one palindromic subarray and the remaining pieces close up. Find the fewest operations to empty the array.
Problem
Given an integer array arr, in one move you may remove a non-empty contiguous subarray that is a palindrome; the remaining elements concatenate. Return the minimum number of moves to delete the entire array.
Input
An integer array arr.
Output
An integer: the minimum number of palindrome removals.
Constraints
- 1 <= arr.length <= 100
- 1 <= arr[i] <= 20
Examples
Example 1
Input
arr = [1,2]
Output
2
Remove each element separately; no multi-element palindrome exists.
Example 2
Input
arr = [1,3,4,1,5]
Output
3
Remove 4, then 1,3,1 (palindrome), then 5.