题目描述
给你一个长度为 n
的整数数组 nums
和一个 正 整数 k
。
一个整数数组的 能量 定义为和 等于 k
的子序列的数目。
请你返回 nums
中所有子序列的 能量和。
由于答案可能很大,请你将它对 10^9 + 7
取余 后返回。
样例
输入:nums = [1,2,3], k = 3
输出:6
解释:
总共有 5 个能量不为 0 的子序列:
子序列 [1,2,3] 有 2 个和为 3 的子序列:[1,2,3] 和 [1,2,3]。
子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3]。
子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3]。
子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3]。
子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3]。
所以答案为 2 + 1 + 1 + 1 + 1 = 6。
输入:nums = [2,3,3], k = 5
输出:4
解释:
总共有 3 个能量不为 0 的子序列:
子序列 [2,3,3] 有 2 个子序列和为 5:[2,3,3] 和 [2,3,3]。
子序列 [2,3,3] 有 1 个子序列和为 5:[2,3,3]。
子序列 [2,3,3] 有 1 个子序列和为 5:[2,3,3]。
所以答案为 2 + 1 + 1 = 4 。
输入:nums = [1,2,3], k = 7
输出:0
解释:不存在和为 7 的子序列,所以 nums 的能量和为 0。
限制
1 <= n <= 100
1 <= nums[i] <= 10^4
1 <= k <= 100
算法1
(动态规划) $O(n^2k)$
- 设状态 $f(i, j, s)$ 表示前 $i$ 个数字中,选择了 $j$ 个数字组成和为 $s$ 的方案数。其中 $i$ 的有效下标范围为 $[1, n]$,$s$ 的有效下标范围为 $[0, k]$。
- 初始时,$f(i, 0, 0) = 1$,其余为 $0$ 待定。
- 转移时,对于 $nums(i)$ 和状态 $f(i, j, s)$,可以不选择 $nums(i)$,则转移 $f(i, j, s) = f(i, j, s) + f(i - 1, j, s)$。当 $nums(i) \le k$ 时,可以选择 $nums(i)$,转移 $f(i, j, s) = f(i, j, s) + f(i - 1, j - 1, s - nums(i))$。
- 最终,由于每个长度为 $j$ 的子序列,可以贡献 $2^{n-j}$ 到答案中(父子序列)。故枚举 $j$,累加答案 $f(n, j, k) \cdot 2^{n-j}$。
- 注意到,由于 $i$ 这一维每轮转移只和前一维相关,所以可以通过倒序枚举 $j$ 和 $s$,省略掉第一维。
时间复杂度
- 动态规划的状态数为 $O(n^2k)$,转移时间为常数,故总时间复杂度为 $O(n^2k)$。
空间复杂度
- 空间优化后,仅需要 $O(nk)$ 的额外空间存储动态规划的状态数和预处理的 2 的幂次。
C++ 代码
#define LL long long
const int N = 110;
class Solution {
private:
int f[N][N], power[N];
public:
int sumOfPower(vector<int>& nums, int k) {
const int n = nums.size();
const int mod = 1000000007;
power[0] = 1;
for (int i = 1; i < n; i++)
power[i] = power[i - 1] * 2 % mod;
memset(f, 0, sizeof(f));
f[0][0] = 1;
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j >= 1; j--) {
int x = nums[i - 1];
for (int s = k; s >= x; s--)
f[j][s] = (f[j][s] + f[j - 1][s - x]) % mod;
}
for (int j = 1; j <= n; j++)
ans = (ans + (LL)(f[j][k]) * power[n - j]) % mod;
return ans;
}
};
算法2
(动态规划) $O(nk)$
- 设状态 $f(i, j)$ 表示前 $i$ 个数字中,能量和为 $j$ 的方案数。其中 $i$ 的有效下标范围为 $[1, n]$,$j$ 的有效下标范围为 $[0, k]$。
- 初始时,$f(0, 0) = 1$,其余为 $0$ 待定。
- 转移时,对于 $nums(i)$ 和状态 $f(i, j)$,可以直接先转移 $f(i, j) = 2 * f(i, j)$,这是因为之前合法的子序列在父子序列不包含 $nums(i)$ 的时候仍然是合法的。在包含 $nums(i)$ 的父子序列中,之前合法的子序列也都是合法的。当 $j \le nums(i)$ 时,可以选择在子序列中包含 $nums(i)$,则转移 $f(i, j) = f(i, j) + f(i - 1, j - nums(i))$。
- 最终答案为 $f(n, k)$。
- 注意到,由于 $i$ 这一维每轮转移只和前一维相关,所以可以通过倒序枚举 $j$,省略掉第一维。
时间复杂度
- 动态规划的状态数为 $O(nk)$,转移时间为常数,故总时间复杂度为 $O(nk)$。
空间复杂度
- 空间优化后,仅需要 $O(k)$ 的额外空间存储动态规划的状态数。
C++ 代码
class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
const int n = nums.size();
const int mod = 1000000007;
vector<int> f(k + 1, 0);
f[0] = 1;
for (int i = 0; i < n; i++)
for (int j = k; j >= 0; j--) {
f[j] = 2 * f[j] % mod;
if (j >= nums[i])
f[j] = (f[j] + f[j - nums[i]]) % mod;
}
return f[k];
}
};