Minimum Cost to Split an Array

hard dp counting

Problem

Split nums into contiguous subarrays. A subarray's importance is k plus its trimmed length, where the trimmed length drops any element that appears exactly once in that subarray. Return the minimum possible sum of importances over all ways to split.

Inputnums = [1,2,1,2,1,3,3], k = 2

Output8

dp[i] = min over j of dp[j] + k + (count of elements in nums[j..i-1] that appear ≥ 2 times).

nums

def min_cost(nums, k):
    n = len(nums)
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        freq = {}
        trimmed = 0                     # elements seen 2+ times in nums[j..i-1]
        for j in range(i - 1, -1, -1):  # extend window leftward
            v = nums[j]
            freq[v] = freq.get(v, 0) + 1
            if freq[v] == 2:
                trimmed += 2            # both copies now count
            elif freq[v] > 2:
                trimmed += 1
            if dp[j] != INF:
                dp[i] = min(dp[i], dp[j] + k + trimmed)
    return dp[n]

function minCost(nums, k) {
  const n = nums.length;
  const INF = Infinity;
  const dp = new Array(n + 1).fill(INF);
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    const freq = new Map();
    let trimmed = 0;
    for (let j = i - 1; j >= 0; j--) {
      const v = nums[j];
      const f = (freq.get(v) || 0) + 1;
      freq.set(v, f);
      if (f === 2) trimmed += 2;
      else if (f > 2) trimmed += 1;
      if (dp[j] !== INF) dp[i] = Math.min(dp[i], dp[j] + k + trimmed);
    }
  }
  return dp[n];
}

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int[] freq = new int[n];
            int trimmed = 0;
            for (int j = i - 1; j >= 0; j--) {
                int v = nums[j];
                freq[v]++;
                if (freq[v] == 2) trimmed += 2;
                else if (freq[v] > 2) trimmed += 1;
                if (dp[j] != Integer.MAX_VALUE)
                    dp[i] = Math.min(dp[i], dp[j] + k + trimmed);
            }
        }
        return dp[n];
    }
}

int minCost(vector<int>& nums, int k) {
    int n = nums.size();
    const int INF = INT_MAX;
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        vector<int> freq(n, 0);
        int trimmed = 0;
        for (int j = i - 1; j >= 0; j--) {
            int v = nums[j];
            freq[v]++;
            if (freq[v] == 2) trimmed += 2;
            else if (freq[v] > 2) trimmed += 1;
            if (dp[j] != INF) dp[i] = min(dp[i], dp[j] + k + trimmed);
        }
    }
    return dp[n];
}

Explanation

We split the array into contiguous pieces and each piece costs k plus its trimmed length — the number of elements that are not unique in that piece (anything appearing twice or more keeps counting). The goal is to minimize the total cost over all pieces. (The problem guarantees values are in 0..n-1, so we can index a frequency array directly.)

Let dp[i] = the minimum cost to split the first i elements. Base case dp[0] = 0. The last piece ends at i and starts at some j, so dp[i] = min over j of dp[j] + cost(nums[j..i-1]).

The trick is computing the last piece's cost without re-scanning. For a fixed i we extend the window leftward, j from i-1 down to 0, maintaining a frequency map. When an element's count first hits 2 both of its copies become "non-unique", so trimmed jumps by 2; every further copy adds 1 more.

So with the running trimmed the candidate dp[j] + k + trimmed is available in O(1) as we move j. We take the best over all j. Overall the two nested loops make it O(n²).

Example: nums = [1,2,1,2,1,3,3], k = 2. The optimal split achieves a total importance of 8.

Time: O(n²) Space: O(n)