Leetcode 3098. Find the Sum of Subsequence Powers

• Leetcode 3098. Find the Sum of Subsequence Powers
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3098. Find the Sum of Subsequence Powers

1. 解题思路

这一题思路上的话还是比较直接的，由于我们只需要求出每一个可能的power值，然后求出对应的power值下所有可能的长度为k的序列的总数，将两者相乘之后求和即可得到我们最终的答案。

其中，对于所有可能的power值得获取是一个简单的操作，我们只需要将数组进行一个二重遍历即可获得所有的可能power得值。

然后，剩下的问题就变成了如何求某个确定的power值$p$下长度为$k$的序列的个数了，这个问题还是比较复杂的，但是我们可以将其进行一下转化，变为：

• 求长度为$k$，且power值不小于$p$的序列的个数。

此时，由于我们已知所有的power值得可能性，因此，power恰好为$p$的序列个数$f(p)$就是上述结果减去$f(q)$，其中，$q$为可取到的第一个比$p$大的power值。

因此，我们只需要完成长度为$k$，且power值不小于$p$的序列的个数的求取即可，而这个问题我们将数列排序之后通过动态规划即可实现。

2. 代码实现

给出python代码实现如下：

MOD = 10**9+7

class Solution:
    def sumOfPowers(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums = sorted(nums)
        delta = set()
        for i in range(n-1):
            for j in range(i+1, n):
                delta.add(nums[j]-nums[i])
        delta = sorted(delta, reverse=True)
                
        @lru_cache(None)
        def dp(idx, md, k, pre):
            if k == 0:
                return 1
            if n-idx < k:
                return 0
            if pre is not None and nums[idx] - pre < md:
                return dp(idx+1, md, k, pre) % MOD
            else:
                return (dp(idx+1, md, k, pre) + dp(idx+1, md, k-1, nums[idx])) % MOD
        
        ans = 0
        s = 0
        for d in delta:
            cnt = dp(0, d, k, None)
            ans = (ans + d * (cnt-s)) % MOD
            s = cnt
        return ans             

提交代码评测得到：耗时796ms，占用内存329.2MB。