Solution

Method 1 – Dynamic Programming with Hash Map

Intuition

We use dynamic programming to find the minimum cost to split the array. For each possible split, we calculate the cost of the subarray using a hash map to count frequencies, then recursively compute the minimum cost for the rest of the array.

Approach

Use DP: dp[i] is the minimum cost to split the first i elements.
For each position i, try all possible previous split points j:
- Use a hash map to count frequencies in nums[j:i].
- Compute the trimmed length (count of elements with freq > 1).
- The cost for subarray [j, i-1] is k + trimmed_len.
- Update dp[i] as the minimum over all splits.
Return dp[n] for the answer.

Code

Related Tags