# 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

遍历所有 上一个subarray的结尾 再加上新的cost 就能找到最小的```dp[i]```
## Code

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];
}
}