网站建设文献综述,青海保险网站建设公司,cdn wordpress 统计,手游传奇网站999服题目#xff1a;
给你一个整数数组 nums 和一个整数 k 。
将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。
令 trimmed(subarray) 作为子数组的一个特征#xff0c;其中所有仅出现一次的数字将会被移除。
例如#xff0c;trimmed([3,1,2,4,3,4…题目
给你一个整数数组 nums 和一个整数 k 。
将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。
令 trimmed(subarray) 作为子数组的一个特征其中所有仅出现一次的数字将会被移除。
例如trimmed([3,1,2,4,3,4]) [3,4,3,4] 。 子数组的 重要性 定义为 k trimmed(subarray).length 。
例如如果一个子数组是 [1,2,3,3,3,4,4] trimmed([1,2,3,3,3,4,4]) [3,3,3,4,4] 。这个子数组的重要性就是 k 5 。 找出并返回拆分 nums 的所有可行方案中的最小代价。
子数组 是数组的一个连续 非空 元素序列。
示例 1
输入nums [1,2,1,2,1,3,3], k 2 输出8 解释将 nums 拆分成两个子数组[1,2], [1,2,1,3,3] [1,2] 的重要性是 2 (0) 2 。 [1,2,1,3,3] 的重要性是 2 (2 2) 6 。 拆分的代价是 2 6 8 可以证明这是所有可行的拆分方案中的最小代价。 示例 2
输入nums [1,2,1,2,1], k 2 输出6 解释将 nums 拆分成两个子数组[1,2], [1,2,1] 。 [1,2] 的重要性是 2 (0) 2 。 [1,2,1] 的重要性是 2 (2) 4 。 拆分的代价是 2 4 6 可以证明这是所有可行的拆分方案中的最小代价。 示例 3
输入nums [1,2,1,2,1], k 5 输出10 解释将 nums 拆分成一个子数组[1,2,1,2,1]. [1,2,1,2,1] 的重要性是 5 (3 2) 10 。 拆分的代价是 10 可以证明这是所有可行的拆分方案中的最小代价。
提示
1 nums.length 1000 0 nums[i] nums.length 1 k 10^9
java代码
class Solution {public int minCost(int[] nums, int k) {int n nums.length;int[] f new int[n 1];byte[] state new byte[n];for (int i 0; i n; i) {Arrays.fill(state, (byte) 0);int unique 0, mn Integer.MAX_VALUE;for (int j i; j 0; --j) {int x nums[j];if (state[x] 0) { // 首次出现state[x] 1;unique;} else if (state[x] 1) { // 不再唯一state[x] 2;--unique;}mn Math.min(mn, f[j] - unique);}f[i 1] k mn;}return f[n] n;}
}
