题目描述：
给你一个整数数组 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\le nums.len \le 1000, 0 \le nums[i] \lt nums.len, 1\le k \le 10^9$
题解：
划分型dp：
两种方法，我比较常用的是设 $dp[i]$ 表示区间 $[1, i]$ 的代价， $dp[0] = 0$ ，然后枚举上一段区间的终点 $j$ ， $dp[i] = \min(dp[i], dp[j] + cost[j + 1, i]), j\in[0, i - 1]$
注意如何计算 $cost[j + 1, i]$ ，因为下标变成从 $1$ 开始了，所以该区间对应到原来数组为 $[j, i - 1]$ 。
考虑如何递推计算区间代价，倒着枚举 $j$ 的话，可以递推处理，每次往最后一段区间中增加一个 $j + 1$ 。增加的数字就是 $nums[j + 1 - 1] = nums[j]$ 。
考虑计算区间中独立数字的个数，然后区间代价就是区间长度减去独立数字个数然后加上 $k$ ，即 $i - j - cost + k$ 。
第二种方法是使用 $dp[i + 1]$ 表示区间 $[0, i]$ 的代价， $dp[-1 + 1] = 0$ ，枚举最后一段区间的起点 $j$ ， $dp[i + 1] = \min(dp[i + 1], dp[j - 1 + 1] + cost[j, i]), j\in[0, i]$
每次往最后一段里面加入 $nums[j]$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minCost(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> dp(n + 1, INF);
vector<int> vis(n);
int cost;
dp[0] = 0;
for (int i = 1; i <= n; ++i)
{
fill(vis.begin(), vis.end(), 0);
cost = 0;
for (int j = i - 1; j >= 0; --j)
{
if (vis[nums[j]] == 0)
cost++;
if (vis[nums[j]] == 1)
cost--;
vis[nums[j]]++;
dp[i] = min(dp[i], dp[j] + (i - j) - cost + k);
}
}
return dp[n];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minCost(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> dp(n + 1, INF);
vector<int> vis(n);
int cost;
dp[0] = 0;
for (int i = 0; i < n; ++i)
{
fill(vis.begin(), vis.end(), 0);
cost = 0;
for (int j = i; j >= 0; --j)
{
if (vis[nums[j]] == 0)
cost++;
if (vis[nums[j]] == 1)
cost--;
vis[nums[j]]++;
dp[i + 1] = min(dp[i + 1], dp[j] + (i - j + 1) - cost + k);
}
}
return dp[n];
}
};
|