这道题的核心思路是排序 记忆化搜索Memoization DFS。题目思路关键观察- 子序列的能量 子序列中任意两个元素差值绝对值的最小值- 子序列的顺序不影响结果所以可以先排序- 排序后子序列的能量一定等于相邻两个元素的差值的最小值DFS 状态设计定义 dfs(i, j, k, mi)- i当前处理到第 i 个元素- j上一个选择的元素的下标j n 表示还没选过- k还需要选多少个元素- mi当前已选元素中的最小差值转移- 不选第 i 个dfs(i1, j, k, mi)- 选第 i 个- 如果 j n第一次选dfs(i1, i, k-1, mi)- 否则更新最小差值dfs(i1, i, k-1, min(mi, nums[i] - nums[j]))记忆化用 HashMap 缓存状态key 编码为 mi 18 | i 12 | j 6 | k。Java 实现javaclass Solution {private MapLong, Integer memo new HashMap();private final int MOD (int) 1e9 7;private int[] nums;private int n;public int sumOfPowers(int[] nums, int k) {Arrays.sort(nums);this.nums nums;this.n nums.length;return dfs(0, n, k, Integer.MAX_VALUE);}/*** param i 当前处理到第 i 个元素* param j 上一个选择的元素的下标n 表示还没选过* param k 还需要选 k 个元素* param mi 当前已选元素中的最小差值* return 从当前状态出发所有合法子序列的能量和*/private int dfs(int i, int j, int k, int mi) {// 所有元素处理完毕if (i n) {// 如果恰好选了 k 个返回当前能量否则返回 0不合法return k 0 ? mi : 0;}// 剪枝即使剩下的元素全选也不够 k 个if (n - i k) {return 0;}// 编码状态为 keylong key ((long) mi 18) | ((long) i 12) | ((long) j 6) | k;if (memo.containsKey(key)) {return memo.get(key);}// 不选第 i 个元素long ans dfs(i 1, j, k, mi);// 选第 i 个元素if (j n) {// 第一次选没有前一个元素不更新 mians dfs(i 1, i, k - 1, mi);} else {// 更新最小差值ans dfs(i 1, i, k - 1, Math.min(mi, nums[i] - nums[j]));}ans % MOD;memo.put(key, (int) ans);return (int) ans;}}复杂度分析指标 复杂度时间 O(n⁵)状态数为 O(n⁴)每个状态 O(1) 转移空间 O(n⁵)记忆化存储的状态数其中 n ≤ 50所以实际运行完全可行。关键点总结1. 先排序排序后子序列的能量只与相邻元素的差值有关2. 状态压缩 keymi 18 | i 12 | j 6 | k用位运算编码四个状态变量3. 剪枝n - i k 时直接返回 04. 边界处理k 0 时返回当前能量 mij n 表示还没选过元素5. 取模每次加法后都要 % MOD 防止溢出
Kimi K2.6 LeetCode 3098. 求出所有子序列的能量和 Java实现
发布时间：2026/6/10 15:13:25
这道题的核心思路是排序 记忆化搜索Memoization DFS。题目思路关键观察- 子序列的能量 子序列中任意两个元素差值绝对值的最小值- 子序列的顺序不影响结果所以可以先排序- 排序后子序列的能量一定等于相邻两个元素的差值的最小值DFS 状态设计定义 dfs(i, j, k, mi)- i当前处理到第 i 个元素- j上一个选择的元素的下标j n 表示还没选过- k还需要选多少个元素- mi当前已选元素中的最小差值转移- 不选第 i 个dfs(i1, j, k, mi)- 选第 i 个- 如果 j n第一次选dfs(i1, i, k-1, mi)- 否则更新最小差值dfs(i1, i, k-1, min(mi, nums[i] - nums[j]))记忆化用 HashMap 缓存状态key 编码为 mi 18 | i 12 | j 6 | k。Java 实现javaclass Solution {private MapLong, Integer memo new HashMap();private final int MOD (int) 1e9 7;private int[] nums;private int n;public int sumOfPowers(int[] nums, int k) {Arrays.sort(nums);this.nums nums;this.n nums.length;return dfs(0, n, k, Integer.MAX_VALUE);}/*** param i 当前处理到第 i 个元素* param j 上一个选择的元素的下标n 表示还没选过* param k 还需要选 k 个元素* param mi 当前已选元素中的最小差值* return 从当前状态出发所有合法子序列的能量和*/private int dfs(int i, int j, int k, int mi) {// 所有元素处理完毕if (i n) {// 如果恰好选了 k 个返回当前能量否则返回 0不合法return k 0 ? mi : 0;}// 剪枝即使剩下的元素全选也不够 k 个if (n - i k) {return 0;}// 编码状态为 keylong key ((long) mi 18) | ((long) i 12) | ((long) j 6) | k;if (memo.containsKey(key)) {return memo.get(key);}// 不选第 i 个元素long ans dfs(i 1, j, k, mi);// 选第 i 个元素if (j n) {// 第一次选没有前一个元素不更新 mians dfs(i 1, i, k - 1, mi);} else {// 更新最小差值ans dfs(i 1, i, k - 1, Math.min(mi, nums[i] - nums[j]));}ans % MOD;memo.put(key, (int) ans);return (int) ans;}}复杂度分析指标 复杂度时间 O(n⁵)状态数为 O(n⁴)每个状态 O(1) 转移空间 O(n⁵)记忆化存储的状态数其中 n ≤ 50所以实际运行完全可行。关键点总结1. 先排序排序后子序列的能量只与相邻元素的差值有关2. 状态压缩 keymi 18 | i 12 | j 6 | k用位运算编码四个状态变量3. 剪枝n - i k 时直接返回 04. 边界处理k 0 时返回当前能量 mij n 表示还没选过元素5. 取模每次加法后都要 % MOD 防止溢出
