3098. 求出所有子序列的能量和 Hard
给你一个长度为 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的子序列的能量和。
分析：
（1）对nums数组排序后，子序列的能量一定由子序列中相邻元素的差值产生；
（2）由（1）可设三维数组dp，dp[i][len][energy]维护以i号元素结尾、长度为k且能量为energy的序列个数。计算dp[i][len]中的值时，可遍历dp[j][len-1][energy]（其中0<=j<i,0<=energy<=MAX_INT），则当energy<abs(nums[i]-nums[j])时，dp[i][len][energy]+=dp[j][len-1][energy]，当energy>=abs(nums[i]-nums[j])时，dp[i][len][abs(nums[i]-nums[j])]+=dp[j][len-1][energy]；
（3）由于energy不可能取到0到MAX_INT所有的值，因此可以用哈希表减少dp数组的存储大小。
class Solution {
public:int sumOfPowers(vector<int>& nums, int k) {int N=nums.size(),mod=1000000007,ans=0;vector<vector<unordered_map<int,int>>> dp(N,vector<unordered_map<int,int>>(k+1));sort(nums.begin(),nums.end());for(int i=0,dis;i<N;++i){dp[i][1][INT_MAX]=1;for(int j=0;j<i;++j){dis=abs(nums[i]-nums[j]);for(int len=2;len<=k;++len){for(const auto& [energy,count]:dp[j][len-1]){int& sum=dp[i][len][min(dis,energy)];sum=(sum+count)%mod;}}}for(const auto&[energy,count]:dp[i][k]) ans=(ans+(long long)energy*count%mod)%mod;}return ans;}
};