求出所有子序列的能量和

题目

求出所有子序列的能量和

---

给你一个长度为 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

题解

方法一:

思路

我们将数组排序，那么最小距离只能是选取的相邻元素。

记忆化搜索，令$f_{p,c,pre,m}$为0到p的数中选了c个，前一个是pre，最小距离是m的所有子序列的最小距离的总和。

答案就是$f_{n-1, k, inf, inf}$

对于每个数选与不选。有转移式$f_{p,c,pre, m} = f_{p-1, c, pre, m} + f_{p-1, c-1, nums[p], min(m, pre-nums[p]}$

代码

class Solution {
public:
    const int MOD = 1e9+7;
    const int INF = 0x3f3f3f3f;
    int sumOfPowers(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        map<vector<int>,int> mp;
        // 0到p个中所有选择c个的最小间距总和, 最近一次选择的是pre,中途的最小间距为mn 
        function<int(int,int,int,int)>  dfs = [&](int p, int c, int pre, int mn) {
            if (mp.count({p, c, pre, mn})) return mp[{p, c, pre, mn}];
            if (c == 0) {
                return mn;
            }
            // 需要c个,还剩p+1个
            if (c>p+1) return 0;
            int res = dfs(p-1, c, pre, mn);
            res += dfs(p-1, c-1, nums[p], min(mn, pre-nums[p]));
            return mp[{p, c, pre, mn}] = res%MOD;
        };
        return dfs(n-1, k, INF, INF);
    }
};