长春市住房城乡建设厅网站,被黑的网站,网络建设公司方案,国家征信系统查询官网Leetcode 3082. Find the Sum of the Power of All Subsequences 1. 解题思路2. 代码实现 题目链接#xff1a;3082. Find the Sum of the Power of All Subsequences
1. 解题思路
这一题的话其实反而还好#xff0c;就是一个比较常规的动态规划的题目。
我们首先需要想明…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 2^{n-k} 2n−k个子序列当中。
因此我们只需要找到所有和为 k 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(idx1, cnt, remain) % MODelse:return (dp(idx1, cnt, remain) dp(idx1, cnt1, remain-nums[idx])) % MODreturn dp(0, 0, k) 提交代码评测得到耗时387ms占用内存122.8MB。
