题目:
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是:将数组划分成两个有序的 组 ,并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ,则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大,请返回对 109 + 7 取余 后的结果。
如果在两个分区中,存在某个元素 nums[i] 被分在不同的组中,则认为这两个分区不同。
示例 1:
输入:nums = [1,2,3,4], k = 4
输出:6
解释:好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
示例 2:
输入:nums = [3,3,3], k = 4
输出:0
解释:数组中不存在好分区。
示例 3:
输入:nums = [6,6], k = 2
输出:2
解释:可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。
提示:
1 <= nums.length, k <= 1000
1 <= nums[i] <= 10^9
java代码:
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countPartitions(int[] nums, int k) {
var sum = 0L;
for (var x : nums) sum += x;
if (sum < k * 2) return 0;
var ans = 1;
var f = new int[k];
f[0] = 1;
for (var x : nums) {
ans = ans * 2 % MOD;
for (var j = k - 1; j >= x; --j)
f[j] = (f[j] + f[j - x]) % MOD;
}
for (var x : f)
ans = (ans - x * 2 % MOD + MOD) % MOD; // 保证答案非负
return ans;
}
}