当前位置：首页 > news >正文

豆包 LeetCode 3082. 求出所有子序列的能量和 Java实现

news 2026/6/17 16:02:52

LeetCode 3082 · 求出所有子序列的能量和

📌 题意理解

数组的能量= 其内部和等于 k 的子序列的个数。

要你求：nums 的所有子序列各自的能量，加起来是多少（mod 1e9+7）。

本质上是「子序列的子序列」计数问题——对每个候选子序列 S（sum(S)=k），它会出现在多少个 nums 的大子序列 T 里？

💡 核心转换（关键洞察）

假设有一个确定的子序列S ⊆ nums，sum(S) = k，|S| = len。

nums 中不包含在 S 里的元素有n - len个，每个可选可不选地塞进 T 里，所以：

S 对答案的贡献 = 2^(n - |S|)

因此：

\text{ans} = \sum_{\substack{S \subseteq \text{nums} \\ \text{sum}(S) = k}} 2^{\,n - |S|}

提出 2ⁿ，等价于追踪每个和为 k 的子序列的2^(-|S|)权重和。

🔑 DP 设计

设dp[j]= 已处理元素中，所有和为 j的子序列对应的2^(-len)的累积和。

初始：dp[0] = 1（空子序列，sum=0，len=0 → 2⁰=1）
处理每个数x时：
- 不选 x：已有子序列仍可存在，且剩余"自由位"多了一位 → 所有 dp 值×2
- 选 x：从dp[j-x]转移过来，选了 x 后长度 +1 → 相当于原来的贡献× ½，即加上dp_old[j-x]

用inv2表示 2 的模逆(MOD+1)/2 = 500000004。

状态转移（一维优化，从后往前）

dp_new[j] = dp_old[j] × 2 ← 不选 x + (j≥x ? dp_old[j-x] : 0) ← 选 x（贡献不变，因为 ×2 和 ×½ 抵消的视角）

实际更干净的形式直接用乘法：

dp[j] = dp[j] \times 2 + (j \ge x ? dp[j-x] : 0)

✅ Java 实现

版本一：一维 DP（推荐，O(n·k) 时间，O(k) 空间）

class Solution { public int sumOfPower(int[] nums, int k) { final int MOD = 1_000_000_007; int n = nums.length; // dp[j] = 所有和为 j 的子序列的累计贡献 // 最终 dp[k] 就是答案 long[] dp = new long[k + 1]; dp[0] = 1; // 空子序列 for (int x : nums) { // 必须从后往前遍历（0-1背包） for (int j = k; j >= 0; j--) { // 不选 x：原有方案依然存在，贡献 ×2（x成了"自由元素"） dp[j] = (dp[j] * 2) % MOD; // 选 x：从和为 j-x 的状态扩展过来 if (j >= x) { dp[j] = (dp[j] + dp[j - x]) % MOD; } } } return (int) dp[k]; } }

版本二：二维 DP（更好理解，O(n·k) 空间）

class Solution { public int sumOfPower(int[] nums, int k) { final int MOD = 1_000_000_007; int n = nums.length; // dp[i][j] = 从前 i 个元素中，选出和为 j 的子序列的总贡献 int[][] dp = new int[n + 1][k + 1]; dp[0][0] = 1; // 空子序列 for (int i = 1; i <= n; i++) { int x = nums[i - 1]; for (int j = 0; j <= k; j++) { // 不选 nums[i-1]：之前的贡献还在，且多了一个自由位 → ×2 dp[i][j] = (int)((dp[i - 1][j] * 2L) % MOD); } for (int j = x; j <= k; j++) { // 选 nums[i-1]：锁定在子序列内，不加自由位，直接累加 dp[i][j] = (dp[i][j] + dp[i - 1][j - x]) % MOD; } } return dp[n][k]; } }