题目描述：
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。
请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。
由于答案可能会很大，将答案对 $10^9 + 7$ 取余 后返回。
数据范围：
$2\le n \le 50, 2\le k \le n$
题解：
子序列，可以直接排序，然后就只需要考虑相邻两个元素的差值即可。
设计动态规划， $dp[i][k]$ 肯定需要，表示 $[0, i]$ 中以 $i$ 结尾的长度为 $k$ 的子序列的能量和。
另一个状态就不好想了。另一个状态为当前序列的能量值， $dp[i][k][v]$ 表示以 $i$ 结尾的长度为 $k$ ，并且能量值为 $v$ 的个数，那么答案就是 $dp[i][k][v] \times v$ 。
枚举子序列中的前一个数字 $j$ ，则 $dp[i][k][\min(v, diff)] = dp[i][k][\min(v, diff)] + dp[j][k - 1][v]$
枚举子序列中的前一个数字 $j$ ，并且遍历所有的 $v$ ，然后更新 $i$ 。
需要四层循环， $O(n^4)$ 。
但是需要注意怎么存 $v$ ，以及初始条件。有点类似上一道题目，都是需要存起来所有的值。
这里可以直接使用 $map$ 。
代码：
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
39
40
41
42
43
| 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 static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int sumOfPowers(vector<int> &nums, int k)
{
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<unordered_map<int, int>>> dp(n, vector<unordered_map<int, int>>(k + 1)); // dp[i][j][k] -> map[k] -> v
for (int i = 0; i < n; ++i) {
dp[i][1][INF] = 1;
for (int kk = 1; kk <= k; ++kk) {
for (int j = 0; j < i; ++j) {
for(auto& [v, value]: dp[j][kk - 1]) {
dp[i][kk][min(v, nums[i] - nums[j])] = (dp[i][kk][min(v, nums[i] - nums[j])] + value) % mod;
}
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for(auto& [v, value]: dp[i][k]) {
ans = (ans + 1ll * dp[i][k][v] * v % mod) % mod;
}
}
return ans;
}
};
|