| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2019 |
第 329 场周赛 Q4 |
|
给你一个整数数组 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 <= 10000 <= nums[i] < nums.length1 <= k <= 109
我们设计一个函数
函数
- 如果
$i \ge n$ ，说明已经拆分到了数组末尾，此时返回$0$ 。 - 否则，我们枚举子数组的末尾
$j$ ，过程中用一个数组或哈希表cnt统计子数组中每个数字出现的次数，用一个变量one统计子数组中出现次数为$1$ 的数字的个数。那么子数组的重要性就是$k + j - i + 1 - one$ ，拆分的代价就是$k + j - i + 1 - one + dfs(j + 1)$ 。我们枚举所有的$j$ ，取其中的最小值作为$dfs(i)$ 的返回值。
过程中，我们可以使用记忆化搜索，即使用一个数组
时间复杂度
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)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;
}
}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);
}
};func minCost(nums []int, k int) int {
n := len(nums)
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] > 0 {
return f[i]
}
ans, one := 1<<30, 0
cnt := make([]int, n)
for j := i; j < n; j++ {
cnt[nums[j]]++
x := cnt[nums[j]]
if x == 1 {
one++
} else if x == 2 {
one--
}
ans = min(ans, k+j-i+1-one+dfs(j+1))
}
f[i] = ans
return ans
}
return dfs(0)
}function minCost(nums: number[], k: number): number {
const n = nums.length;
const f = new Array(n).fill(0);
const dfs = (i: number) => {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
const cnt = new Array(n).fill(0);
let one = 0;
let ans = 1 << 30;
for (let j = i; j < n; ++j) {
const 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));
}
f[i] = ans;
return f[i];
};
return dfs(0);
}