Leetcode 3082. Find the Sum of the Power of All Subsequences

本文主要是介绍Leetcode 3082. Find the Sum of the Power of All Subsequences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• Leetcode 3082. Find the Sum of the Power of All Subsequences
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3082. Find the Sum of the Power of All Subsequences

1. 解题思路

这一题的话其实反而还好，就是一个比较常规的动态规划的题目。

我们首先需要想明白一点，虽然题目中是要在所有的子序列当中找到所有和为k的子子序列，但是我们实际做的时候可以反过来思考，考察和为k的子序列能够出现在哪些子序列当中，考察其出现的频次即可。

此时，假设目标长度为k，而总的字符串长度为n，则对应的这个子序列可以存在在$2^{n-k}$个子序列当中。

因此，我们只需要找到所有和为$k$的子序列即可，而这也就是一个比较常规的动态规划的题目了。

2. 代码实现

给出python代码实现如下：

MOD = 10**9 + 7
FACTS = [1]
for _ in range(100):FACTS.append(FACTS[-1] * 2 % MOD)class Solution:def sumOfPower(self, nums: List[int], k: int) -> int:n = len(nums)@lru_cache(None)def dp(idx, cnt, remain):if remain == 0:return FACTS[n-cnt]elif idx >= n:return 0elif nums[idx] > remain:return dp(idx+1, cnt, remain) % MODelse:return (dp(idx+1, cnt, remain) + dp(idx+1, cnt+1, remain-nums[idx])) % MODreturn dp(0, 0, k) 

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

这篇关于Leetcode 3082. Find the Sum of the Power of All Subsequences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---