LC-2518.好分区的数目

题目描述

leetcode 困难题

给你一个正整数数组 nums 和一个整数 k 。

分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。

返回 不同 的好分区的数目。由于答案可能很大，请返回对 10^9 + 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]) 。

提示1：

1 <= nums.length, k <= 1000
1 <= nums[i] <= 10^9

反向思维

该题的关键在于，由于 $nums[i]$ 能取到 $10^9$ ，也就是说子序列的元素和最大能取到 $10^{12}$ ，我们很难定义该容量的背包，所以需要对原问题进行转化，尝试将原问题转化成求所有坏分区的数目，此时用总分区数目减去坏分区数目即为原问题答案。

当数组总和小于 $2*k$ 时，显然无论怎么划分都无法得出好分区，所以可以提前返回 $0$ 。

我们可以先尝试求出元素总和小于 $k$ 的子序列数目，由于 $k$ 最大取到 $1000$ ，所以通过背包 $dp$ 就能很容易的求出该数目。

设元素总和小于 $k$ 的子序列数目为 $badCnt$ ，由于对于数组总和小于 $2*k$ 的用例我们都直接返回，所以此时这些坏序列所对应的另一半序列的和，都必然是大于 $k$ 的，也就是说不存在互相配对的情况，而又因为该子序列可以是分区的左边或者右边，所以此时坏分区的数目就为 $2 * badCnt$ 。

class Solution {
    private final int MOD = (int)(1e9 + 7);

    public int countPartitions(int[] nums, int k) {
        if(Arrays.stream(nums).mapToLong(Long::valueOf).sum() < 2L * k){
            return 0;
        }
        long allCnt = 1;
        long[] dp = new long[k];
        dp[0] = 1;
        for(int i = 1; i < nums.length + 1; i++){
            allCnt = (allCnt * 2) % MOD;
            for(int j = k - nums[i - 1] - 1; j >= 0 ; j--){
                dp[j + nums[i - 1]] = (dp[j + nums[i - 1]] + dp[j]) % MOD;
            }
        }
        long badCnt = 0;
        for(long i : dp){
            badCnt = (badCnt + i) % MOD;
        }
        badCnt = (badCnt * 2) % MOD;
        return (int)((allCnt - badCnt + MOD) % MOD);
    }
}