好分区的数目

标签: 数组 动态规划

难度: Hard

给你一个正整数数组 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] <= 109

Submission

运行时间: 83 ms

内存: 16.2 MB

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        if sum(nums) < k * 2: return 0
        MOD = 10 ** 9 + 7
        f = [0] * k
        f[0] = 1
        for x in nums:
            for j in range(k - 1, x - 1, -1):
                f[j] = (f[j] + f[j - x]) % MOD
        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD

Explain

这道题解的核心是使用动态规划来确定可以形成好分区的组合数。首先，如果数组总和小于2*k，则不可能形成两个组，每个组的和都至少为k。因此，如果数组和小于2*k，直接返回0。使用一个动态规划数组f，其中f[j]表示通过选择部分元素能够形成和为j的方式数。初始化f[0]=1，表示和为0的方式有一种（即一个元素都不选）。遍历数组中的每个元素x，从k-1向下至x更新f数组，f[j]更新为f[j]和f[j-x]的和，即考虑不选x和选x两种情况。最后，计算所有可能的分区方式，即2的nums长度次方，减去那些不符合好分区的情况（即两个分区中至少有一个的和小于k的情况，这些情况的总数是f数组中从1到k-1的元素的两倍），然后对结果取模。

时间复杂度: O(n*k)

空间复杂度: O(k)

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        if sum(nums) < k * 2: return 0  # 如果数组总和小于2*k，直接返回0
        MOD = 10 ** 9 + 7  # 定义模数
        f = [0] * k  # 动态规划数组，大小为k
        f[0] = 1  # 初始化f[0]，和为0的方式数为1
        for x in nums:  # 遍历数组中的每个元素
            for j in range(k - 1, x - 1, -1):  # 从k-1到x更新动态规划数组
                f[j] = (f[j] + f[j - x]) % MOD  # 更新f[j]，考虑选或不选x
        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD  # 计算结果并取模

Explore

在动态规划中从k-1向下至x更新数组f是为了避免元素x在同一次遍历中被重复使用。如果从x向上到k-1更新，当前元素x的加入可能会立即影响到基于它自身之前的值计算出的新值，这会导致某些数值被重复计算多次，违背了每个元素仅用一次的原则。从高到低的更新确保当处理到f[j]时，f[j-x]仍然是没有加上当前元素x之前的状态，从而保持了状态的正确转移。

动态规划数组f中的f[0]=1表示和为0的方式有一种，即不选择任何元素的情况。这是基本的边界条件，作为动态规划解决子问题的基础。对于其他索引的值初始化为0，是因为在开始时，没有任何元素被选择，因此除了和为0之外，形成其他和的方式数都应该是0，直到遍历到具体的元素并更新这些值。

通过从高到低更新动态规划数组（即从k-1到x），确保在一次元素遍历中，每个元素只被计算一次。这种更新方法意味着在更新f[j]时，依赖的f[j-x]是基于当前元素之前的状态，还未被当前元素影响。这样可以保证每个元素在计算各个状态值时只被使用一次，避免重复计算。

在题解中，不符合好分区的情况是指两个分区中至少有一个的和小于k。动态规划数组f[j]记录的是形成和为j的分区方法数。因此，计算所有不符合条件的分区方案数，就是计算f[1]到f[k-1]的总和，并将此和乘以2，因为每个这样的和都可以出现在两个分区中的任何一个。最后，从总的分区方法数中减去这个乘以2后的数，得到符合条件的分区方法数。