# Minimum Cost to Split an Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-split-an-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-split-an-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Indeed](https://scaleengineer.com/companies/indeed)
---
## Problem
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.

* For example, `trimmed([3,1,2,4,3,4]) = [3,4,3,4].`

The **importance value** of a subarray is `k + trimmed(subarray).length`.

* For example, if a subarray is `[1,2,3,3,3,4,4]`, then trimmed(`[1,2,3,3,3,4,4]) = [3,3,3,4,4].`The importance value of this subarray will be `k + 5`.

Return _the minimum possible cost of a split of_ `nums`.

A **subarray** is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

**Input:** nums = [1,2,1,2,1,3,3], k = 2
**Output:** 8
**Explanation:** We split nums to have two subarrays: [1,2], [1,2,1,3,3].
The importance value of [1,2] is 2 + (0) = 2.
The importance value of [1,2,1,3,3] is 2 + (2 + 2) = 6.
The cost of the split is 2 + 6 = 8. It can be shown that this is the minimum possible cost among all the possible splits.

**Example 2:**

**Input:** nums = [1,2,1,2,1], k = 2
**Output:** 6
**Explanation:** We split nums to have two subarrays: [1,2], [1,2,1].
The importance value of [1,2] is 2 + (0) = 2.
The importance value of [1,2,1] is 2 + (2) = 4.
The cost of the split is 2 + 4 = 6. It can be shown that this is the minimum possible cost among all the possible splits.

**Example 3:**

**Input:** nums = [1,2,1,2,1], k = 5
**Output:** 10
**Explanation:** We split nums to have one subarray: [1,2,1,2,1].
The importance value of [1,2,1,2,1] is 5 + (3 + 2) = 10.
The cost of the split is 10. It can be shown that this is the minimum possible cost among all the possible splits.

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] < nums.length`
* `1 <= k <= 109`

# Approaches
## Naive Dynamic Programming
This approach uses a straightforward dynamic programming formulation. We define `dp[i]` as the minimum cost to split the prefix of the array `nums` of length `i`. To compute `dp[i]`, we consider all possible previous split points `j < i`. The cost would be the minimum cost to split the array up to `j` (`dp[j]`) plus the cost of the newly formed last subarray `nums[j...i-1]`. The main drawback is the repeated and inefficient calculation of the cost for each subarray.
**Time:** O(N^3), where N is the number of elements in `nums`. There are two nested loops for `i` and `j` (O(N^2)), and inside, calculating the cost of a subarray takes O(N) time. · **Space:** O(N), where N is the number of elements in `nums`. This is for the `dp` array and the frequency count array used inside the loops.
**Pros:** It is a direct translation of the problem's recurrence relation, making it relatively easy to understand and implement.
**Cons:** The time complexity of O(N^3) is too slow for the given constraints (N <= 1000), and this solution will likely result in a 'Time Limit Exceeded' error.
### Explanation
The recurrence relation for this DP approach is `dp[i] = min_{0 <= j < i} (dp[j] + cost(nums[j...i-1]))`. The `cost` of a subarray `nums[j...i-1]` is `k + trimmed(nums[j...i-1]).length`. 

To implement this, we use two nested loops to iterate through all possible start (`j`) and end (`i`) points of the subarrays. For each subarray, we perform another loop to calculate the frequency of its elements to determine the `trimmed_length`. This three-level nested loop structure leads to a cubic time complexity.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // Subarray is nums[j...i-1]
                // Since 0 <= nums[i] < nums.length, an array can be used instead of a HashMap
                int[] counts = new int[n];
                for (int l = j; l < i; l++) {
                    counts[nums[l]]++;
                }

                int trimmedLength = 0;
                // This loop can be optimized, but overall complexity remains O(N^3)
                for (int count : counts) {
                    if (count > 1) {
                        trimmedLength += count;
                    }
                }

                long cost = k + trimmedLength;
                if (dp[j] != Long.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + cost);
                }
            }
        }
        return (int) dp[n];
    }
}
```
### Algorithm
- Create a `dp` array of size `n+1`, where `n` is the length of `nums`. `dp[i]` will store the minimum cost to split the prefix `nums[0...i-1]`.
- Initialize `dp[0] = 0` and all other `dp[i]` to a very large value.
- Iterate `i` from `1` to `n`:
  - For each `i`, iterate `j` from `0` to `i-1`. This `j` represents a potential split point, making `nums[j...i-1]` the last subarray.
  - For each subarray `nums[j...i-1]`, calculate its cost:
    - Create a frequency map (or an array since element values are bounded) for the elements in `nums[j...i-1]` by iterating from `j` to `i-1`.
    - Calculate `trimmed_length` by iterating through the frequency map and summing up the counts of elements that appear more than once.
    - The cost of the subarray is `k + trimmed_length`.
  - Update the `dp` state: `dp[i] = min(dp[i], dp[j] + cost)`.
- The final answer is `dp[n]`.

## Optimized Dynamic Programming
This approach refines the naive DP solution by optimizing the calculation of subarray costs. The core DP state and recurrence remain the same, but we avoid recomputing the `trimmed_length` from scratch for every subarray. By iterating backwards for the start of the last subarray, we can incrementally update the `trimmed_length` in constant time for each new element added. This optimization reduces the overall time complexity from cubic to quadratic.
**Time:** O(N^2), where N is the number of elements in `nums`. The two nested loops dominate the runtime, and the operations inside are O(1). · **Space:** O(N), for the `dp` array and the `counts` frequency array.
**Pros:** The O(N^2) complexity is efficient enough to solve the problem within typical time limits for N up to 1000.; It's a common and powerful optimization technique for this class of DP problems.
**Cons:** While efficient enough for the given constraints, an O(N^2) solution might still be too slow for significantly larger inputs.
### Explanation
The key insight is that for a fixed endpoint `i`, as we consider different start points `j`, the subarrays `nums[j...i-1]` are related. Specifically, `nums[j...i-1]` is just `nums[j+1...i-1]` with `nums[j]` prepended. 

We can exploit this. For a fixed `i`, we iterate `j` from `i-1` down to `0`. We maintain the `trimmed_length` of the subarray `nums[j...i-1]`. When we move from `j` to `j-1`, we are essentially adding `nums[j-1]` to our subarray. The change in `trimmed_length` depends only on the number of times `nums[j-1]` has already appeared in `nums[j...i-1]`. This update can be done in O(1) time with a frequency map. This eliminates the innermost O(N) loop from the naive approach.

```java
import java.util.Arrays;

class Solution {
    public int minCost(int[] nums, int k) {
        int n = nums.length;
        long[] dp = new long[n + 1];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            int[] counts = new int[n]; // Since 0 <= nums[i] < nums.length
            int trimmedLength = 0;
            for (int j = i - 1; j >= 0; j--) {
                int num = nums[j];
                counts[num]++;
                if (counts[num] == 2) {
                    trimmedLength += 2;
                } else if (counts[num] > 2) {
                    trimmedLength += 1;
                }
                
                long cost = k + trimmedLength;
                if (dp[j] != Long.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + cost);
                }
            }
        }
        return (int) dp[n];
    }
}
```
Note: We use a `long` array for `dp` because intermediate costs `dp[j] + cost` can exceed `Integer.MAX_VALUE` given the constraints on `k`, even though the final answer is guaranteed to fit in an `int`.
### Algorithm
- Use the same DP state `dp[i]` as the naive approach, representing the minimum cost for the prefix `nums[0...i-1]`.
- Initialize `dp[0] = 0` and other `dp` entries to a large value.
- Iterate `i` from `1` to `n`:
  - To calculate `dp[i]`, we will consider all subarrays `nums[j...i-1]` ending at `i-1`.
  - Instead of a forward `j` loop, we loop `j` backwards from `i-1` down to `0`.
  - Maintain a frequency array `counts` and a running `trimmedLength` for the current subarray being considered.
  - In the inner loop (for `j`):
    - Add `nums[j]` to the current subarray (which was `nums[j+1...i-1]`).
    - Update the frequency of `nums[j]` in `counts`.
    - Update `trimmedLength` based on the new count of `nums[j]`. If the count becomes 2, `trimmedLength` increases by 2. If it's greater than 2, it increases by 1.
    - Calculate the cost `k + trimmedLength` and update `dp[i] = min(dp[i], dp[j] + cost)`.
- Return `dp[n]`.

# Solutions
### Java

```java
class Solution {
private
  Integer[] f;
private
  int[] nums;
private
  int n, k;
public
  int minCost(int[] nums, int k) {
    n = nums.length;
    this.k = k;
    this.nums = nums;
    f = new Integer[n];
    return dfs(0);
  }
private
  int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int[] cnt = new int[n];
    int one = 0;
    int ans = 1 << 30;
    for (int j = i; j < n; ++j) {
      int x = ++cnt[nums[j]];
      if (x == 1) {
        ++one;
      } else if (x == 2) {
        --one;
      }
      ans = Math.min(ans, k + j - i + 1 - one + dfs(j + 1));
    }
    return f[i] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCost(vector<int> &nums, int k) {
    int n = nums.size();
    int f[n];
    memset(f, 0, sizeof f);
    function<int(int)> dfs = [&](int i) {
      if (i >= n) {
        return 0;
      }
      if (f[i]) {
        return f[i];
      }
      int cnt[n];
      memset(cnt, 0, sizeof cnt);
      int one = 0;
      int ans = 1 << 30;
      for (int j = i; j < n; ++j) {
        int x = ++cnt[nums[j]];
        if (x == 1) {
          ++one;
        } else if (x == 2) {
          --one;
        }
        ans = min(ans, k + j - i + 1 - one + dfs(j + 1));
      }
      return f[i] = ans;
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def minCost(self, nums: List[int], k: int) -> int: @ cache def dfs(i): if i >= n: return 0 cnt = Counter() one = 0 ans = inf for j in range(i, n): cnt[nums[j]] += 1 if cnt[nums[j]] == 1: one += 1 elif cnt[nums[j]] == 2: one -= 1 ans = min(ans, k + j - i + 1 - one + dfs(j + 1)) return ans n = len(nums) return dfs(0)

```