建个网站需要多少钱费用,下载小程序安装,easyui网站开发实战电子书,信阳网站建设的费用文章目录 题目思路Java 数学 01背包变种第一步#xff1a;第二步#xff1a;第三步#xff1a; 复杂度Code 题目
Problem: 100241. 求出所有子序列的能量和给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。一个整数数组的 能量 定义为和 等于 k 的子序列的数目。请… 文章目录 题目思路Java 数学 01背包变种第一步第二步第三步 复杂度Code 题目
Problem: 100241. 求出所有子序列的能量和给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。一个整数数组的 能量 定义为和 等于 k 的子序列的数目。请你返回 nums 中所有子序列的 能量和 。由于答案可能很大请你将它对 10 ^ 9 7 取余 后返回。1 n 1001 nums[i] 10 ^ 41 k 100
思路
Java 数学 01背包变种
第一步
首先题目意思是求子序列的子序列和为 k 的总个数接着为了保证数据不重不漏可以按照公式求选 l 个元素和为 k 的所有可能性个数 * 剩下 n - l 个元素选或不选的所有可能性个数。最后由于元素均为正整数因此枚举 l 为 [1, k] 即可
第二步
选 l 个元素和为 k 的所有可能性个数假设忽略 l 个元素即序列和为 k 的个数直接套用 01 背包 dp[i][j] 代表前 i 个元素和为 j 的总个数dp[i][j] dp[i-1][j-nums[l]]nums[l] j k空间优化掉 i倒序遍历 j 即可 然后添加一维 l 代表选 l 个元素最后结果就是 dp[l][k] 可看做 dp[i][l][j] 代表前 i 个元素选择 l 个元素和为 j 的总个数dp[i][l][j] dp[i-1][l-1][j-nums[l]]nums[l] j k代表选择 nums[l] 这个元素空间优化掉 i倒序遍历 j 即可
第三步
剩下 n-l 个元素选或不选的所有可能性个数假设 l1 即选择的元素就是 k此时 n-1 个元素就有 2^(n-1) 种可能性参考实例 1最后注意使用带 mod 的快速幂
复杂度
时间复杂度: 时间复杂度 O ( n k 2 ) O(nk^2) O(nk2) 空间复杂度: 空间复杂度 O ( k 2 ) O(k^2) O(k2) Code
class Solution {/*** Java 数学 01背包变种** 第一步* 首先题目意思是求子序列的子序列和为 k 的总个数* 接着为了保证数据不重不漏可以按照公式求* 选 l 个元素和为 k 的所有可能性个数 * 剩下 n - l 个元素选或不选的所有可能性个数。* 最后由于元素均为正整数因此枚举 l 为 [1, k] 即可** 第二步* 选 l 个元素和为 k 的所有可能性个数* 假设忽略 l 个元素即序列和为 k 的个数直接套用 01 背包* * dp[i][j] 代表前 i 个元素和为 j 的总个数* * dp[i][j] dp[i-1][j-nums[l]]nums[l] j k* * 空间优化掉 i倒序遍历 j 即可* 然后添加一维 l 代表选 l 个元素最后结果就是 dp[l][k]* * 可看做 dp[i][l][j] 代表前 i 个元素选择 l 个元素和为 j 的总个数* * dp[i][l][j] dp[i-1][l-1][j-nums[l]]nums[l] j k代表选择 nums[l] 这个元素* * 空间优化掉 i倒序遍历 j 即可** 第三步* 剩下 n-l 个元素选或不选的所有可能性个数* 假设 l1 即选择的元素就是 k* 此时 n-1 个元素就有 2^(n-1) 种可能性参考实例 1* 最后注意使用带 mod 的快速幂** 时间复杂度Onk^2空间复杂度Ok^2*/public int sumOfPower(int[] nums, int k) {int mod 1_000_000_007;int n nums.length;// 排序让大于 k 的元素直接返回Arrays.sort(nums);// 01 背包变种空间优化后dp[l][j] 代表选 l 个元素和为 j 的所有可能性个数long[][] dp new long[k 1][k 1];// 不选任何元素总和为 0 才需要初始化dp[0][0] 1;for (int i 0; i n nums[i] k; i) {// 01 背包空间优化需要倒序for (int j k; j nums[i]; j--) {for (int l 1; l k 1; l) {dp[l][j] dp[l - 1][j - nums[i]];dp[l][j] % mod;}}}long res 0L;// 选 l 个元素总和为 kfor (int l 1; l k; l) {// 选 l 个元素和为 k 的所有可能性个数 * 剩下 n - l 个元素选或不选的所有可能性个数 *res dp[l][k] * qPow(2L, n - l, mod);res % mod;}return (int) (res % mod);}private long qPow(long value, long pow, long mod) {long res 1;while (pow 0) {if ((pow 1) 1) {res * value;res % mod;}value * value;value % mod;pow 1;}return res;}
}
