Minimum Cost to Split an Array — LeetCode 2547 Python Solution

The problem

You are given an integer array nums and an integer k. Split the array into some number of non-empty subarrays.

Example

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].

Python solution

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)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2547. Minimum Cost to Split an Array is filed here because LeetCode tags it Dynamic Programming, which is the vocabulary this hub collects.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems