求出所有子序列的能量和

2024-07-23

leetcode

题目：

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。一个子序列的能量定义为子序列中任意两个元素的差值绝对值的 最小值 。

请你返回 nums 中长度等于 k 的所有子序列的 能量和 。由于答案可能会很大，将答案对 109 + 7 取余后返回。

示例 1：

输入：nums = [1,2,3,4], k = 3

输出：4

解释：

nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。
示例 2：

输入：nums = [2,2], k = 2

输出：0

解释：

nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。
示例 3：

输入：nums = [4,3,-1], k = 2

输出：10

解释：

nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。

提示：

2 <= n == nums.length <= 50
-108 <= nums[i] <= 108
2 <= k <= n

暴力，但没过全部

思路：

我们可以直接暴力求解，就是复杂度高一点

回溯算法求出所有长度为 k 的子序列，然后对于这些子序列求他们的能力，然后相加就行

代码：

class Solution {
public:
    vector<int> path;
    int ans = 0;
    int mod = 1e9 + 7;
    int getMinAbs() {
        int res = INT_MAX;
        vector<int> temp = path;
        sort(temp.begin(), temp.end());
        for (int i = 0; i < temp.size() - 1; i++) {
            res = min(res, temp[i + 1] - temp[i]);
        }
        return res;
    }
    void backTracking(vector<int>& nums, int k, int i) {
        if (path.size() == k) {
            int power = getMinAbs();
            ans = (ans + power) % mod;
            return;
        }
        for (int j = i; j < nums.size(); j++) {
            path.push_back(nums[j]);
            backTracking(nums, k, j + 1);
            path.pop_back();
        }
    }
    int sumOfPowers(vector<int>& nums, int k) {
        // 回溯，枚举子序列
        // 保留所有子序列的和
        backTracking(nums, k, 0);
        return ans;
    }
};

动态规划，但看不懂

思路：

由于子序列的能量为任意两个元素的差值绝对值的最小值，因此对子序列排序后，其能量为两两相邻元素的差值绝对值的最小值。在对原数组 nums 排序后，我们在计算子序列能量时只需考虑相邻元素之间的差值即可。

采用求解数组最长上升子序列的思想，我们从小到大枚举 i 作为子序列中的最后一个元素，再从 0 到 i − 1 去枚举 j 作为 i 的前置元素，这样一来产生差值 diff =∣nums[i] − nums[j]∣。接着我们再枚举子序列的长度 p，然后考虑从「以 j 结尾且长度为 p − 1 的子序列」等一系列状态进行转移求解。

设 d[i][p][v] 表示以 i 为结尾时，有多少个长度为 p 且能量为 v 的子序列。这样一来，就有如下转移方程：

dp[i][p][v] = sum(d[j][p - 1][v])  for v < diff 
              sum(d[j][p - 1][diff] + d[j][p - 1][diff + 1] + ...) for v = diff
              0  for v > diff
              sum 代表求取0 - i - 1 所有的j

在实现时，我们只需枚举所有 d[j][p−1][v]，然后更新到 d[i][p][min(diff,v)] 即可。
最后，我们枚举所有长度为 k 的状态，并将 v * d[i][k][v] 累加到答案中，即可得到 nums 中长度等于 k 的所有子序列的能量和。

细节
	长度为 n 的整数数组，两两元素之间的差值种类数不会超过 n * (n - 1) / 2，因此状态表示中 v 的数量级大致在 n^2 量级。具体到每个状态 d[i][p][v]，实际可取的 v 更少。因此，在代码实现时可以将 d[i][p] 定义为字典（哈希表），来减少状态枚举数量，并减少代码量。
	将 d[i][1][inf] 初始化为 1，方便后续状态转移，其中 inf 表示无穷大。

代码：

class Solution {
public:
    using ump = unordered_map<int, int>;
    static constexpr int mod = 1e9 + 7;
    static constexpr int inf = 0x3f3f3f3f;
    int sumOfPowers(vector<int>& nums, int k) {
        int n = nums.size();
        int res = 0;
        vector<vector<ump>> d(n, vector<ump>(k + 1));
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++) {
            d[i][1][inf] = 1;
            for (int j = 0; j < i; j++) {
                int diff = abs(nums[i] - nums[j]);
                for (int p = 2; p <= k; p++) {
                    for (auto &[v, cnt] : d[j][p - 1]) {
                        d[i][p][min(diff, v)] = (d[i][p][min(diff, v)] + cnt) % mod;
                    }
                }
            }

            for (auto &[v, cnt] : d[i][k]) {
                res = (res + 1ll * v * cnt % mod) % mod;
            }
        }
        return res;
    }
};