企业官网建设流程全解析

LeetCode 3082 · 求出所有子序列的能量和 (Go实现)

🎯 解题思路

这道题的关键是转换问题：

1. 对每个和为 k 的子序列 S，计算它被多少个大子序列 T 包含

2. 包含 S 的大子序列 T 数量 = 2^(n - |S|)，其中 n 是数组长度

3. 所以答案为所有和为 k 的子序列 S 的 2^(n-|S|) 之和

通过动态规划来计算这个和，使用 0-1 背包的思想。

🧮 动态规划方法

二维 DP（更容易理解）

func sumOfPower(nums []int, k int) int { const MOD = 1_000_000_007 n := len(nums) // dp[i][j] 表示前 i 个元素，和为 j 的子序列的贡献总和 dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, k+1) } dp[0][0] = 1 // 空子序列 for i := 1; i <= n; i++ { x := nums[i-1] for j := 0; j <= k; j++ { // 不选 nums[i-1] dp[i][j] = (dp[i-1][j] * 2) % MOD } for j := x; j <= k; j++ { // 选 nums[i-1] dp[i][j] = (dp[i][j] + dp[i-1][j-x]) % MOD } } return dp[n][k] }

一维 DP（优化空间）

func sumOfPower(nums []int, k int) int { const MOD = 1_000_000_007 // dp[j] 表示和为 j 的子序列的贡献总和 dp := make([]int, k+1) dp[0] = 1 // 空子序列 for _, x := range nums { // 从后向前遍历，避免重复使用同一个元素 for j := k; j >= 0; j-- { // 不选当前元素：已有子序列贡献翻倍 dp[j] = (dp[j] * 2) % MOD // 选当前元素 if j >= x { dp[j] = (dp[j] + dp[j-x]) % MOD } } } return dp[k] }

📊 算法复杂度分析

🔍 测试用例验证

package main import "fmt" func main() { // 测试用例 tests := []struct { nums []int k int want int }{ {[]int{1, 2, 3}, 3, 6}, // 示例1 {[]int{2, 3, 3}, 5, 4}, // 示例2 {[]int{1, 1, 1}, 2, 3}, // 示例3 } for i, test := range tests { result := sumOfPower(test.nums, test.k) if result == test.want { fmt.Printf("测试用例 %d 通过: nums=%v, k=%d, 结果=%d\n", i+1, test.nums, test.k, result) } else { fmt.Printf("测试用例 %d 失败: nums=%v, k=%d, 期望=%d, 实际=%d\n", i+1, test.nums, test.k, test.want, result) } } }

📝 详细推导过程

为什么这样计算？

1. 对于任意和为 k 的子序列 S，长度为 len

2. 包含 S 的大子序列 T 个数 = 2^(n - len)

   • 因为 n-len 个不在 S 中的元素，每个都可以选或不选

3. 所以答案为：∑ (对所有 sum(S)=k 的子序列 S) 2^(n - |S|)

DP 状态转移解释

设处理到第 i 个元素：

• 不选 nums[i]：原有子序列依然存在，而且多了一个"自由元素"位，所以贡献 ×2

• 选 nums[i]：从 dp[j-x] 转移过来，直接累加原有贡献

💡 关键技巧

1. 从后往前遍历：避免重复使用同一个元素，符合 0-1 背包

2. MOD 取模：在每一步乘法加法后都要取模，防止溢出

3. 边界处理：j >= x 时才进行转移，防止数组越界

🎯 总结

这道题的核心是转换视角：

• 从"计算每个子序列的能量"转换为"计算每个固定子序列被多少个大子序列包含"

• 然后通过0-1背包DP计算带权重的子序列计数

最终的一维DP版本是最高效的实现，时间和空间复杂度都达到了最优。