Minimum cost to split an array

Array Hash Table Dynamic Programming Counting

44.1% acceptance

Feb 25, 2026

467

You are given an integer array nums and an integer k. Split the array into some number of non-empty subarrays. The cost of a split is the sum of the importance value of each subarray in the split. Let trimmed(subarray) be the version of the subarray where all numbers which appear only once are removed. The importance value of a subarray is k + trimmed(subarray).length. Return the minimum possible cost of a split of nums. A subarray is a contiguous non-empty sequence of elements within an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as i32;
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;

    for i in 1..=n {
      let mut freq = vec![0usize; n];
      let mut trimmed = 0usize;
      for j in (0..i).rev() {
        let v = nums[j] as usize;
        freq[v] += 1;
        if freq[v] == 2 {
          trimmed += 2;
        } else if freq[v] > 2 {
          trimmed += 1;
        }
        if dp[j] != i32::MAX {
          let importance = k + trimmed as i32;
          dp[i] = dp[i].min(dp[j] + importance);
        }
      }
    }
    dp[n]
  }
}