---
# System prepended metadata

title: 2547. Minimum Cost to Split an Array
tags: [Leetcode, Dynamic Programming, Hard]

---

# 2547. Minimum Cost to Split an Array
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-cost-to-split-an-array/description/
## 思路
基本型II dp
```dp[i]```表示minimum cost to split ```nums[0:i]```
遍历所有 上一个subarray的结尾 再加上新的cost 就能找到最小的```dp[i]```
## Code
```java=
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 curr = k;
            Map<Integer, Integer> map = new HashMap<>();
            for(int j=i; j>=1; j--){
                map.put(nums[j-1], map.getOrDefault(nums[j-1], 0)+1);
                //对于 不只出现一次的元素 出现一次trimmed subarray length就会+1
                if(map.get(nums[j-1])>1) curr += 1;
                //如果刚成为 不只出现一次的元素 trimmed subarray length需要+2
                if(map.get(nums[j-1])==2) curr += 1;
                dp[i] = Math.min(dp[i], curr+dp[j-1]);
            }
        }
        return dp[n];
    }
}
```