我来用Python3实现LeetCode 2518.好分区的数目。解题思路正难则反直接计算好分区困难改为计算不好分区至少一组和k再用总分区数减去。关键点1. 如果数组总和 2*k直接返回02. 用0-1背包计算所有和 k 的子集方案数3. 不好分区数 和k的方案数 × 2因为第一组或第二组都可能和k4. 好分区数 2^n - 不好分区数Python3代码实现class Solution:def countPartitions(self, nums: List[int], k: int) - int:MOD 10**9 7# 如果总和小于2k不可能有好分区if sum(nums) 2 * k:return 0n len(nums)# dp[j]: 选出若干元素和为j的方案数 (j k)dp [0] * kdp[0] 1 # 空集和为0# 0-1背包倒序遍历for x in nums:for j in range(k - 1, x - 1, -1):dp[j] (dp[j] dp[j - x]) % MOD# 计算所有和小于k的方案数bad sum(dp) % MOD# 不好分区数 第一组和k 或 第二组和kbad bad * 2 % MOD# 总分区数 2^ntotal pow(2, n, MOD)# 好分区数 总分区数 - 不好分区数return (total - bad) % MOD代码优化版本更简洁class Solution:def countPartitions(self, nums: List[int], k: int) - int:MOD 10**9 7if sum(nums) 2 * k:return 0dp [0] * kdp[0] 1for x in nums:for j in range(k - 1, x - 1, -1):dp[j] (dp[j] dp[j - x]) % MOD# 总分区数 - 不好分区数return (pow(2, len(nums), MOD) - sum(dp) * 2) % MOD复杂度分析- 时间复杂度O(n × k)其中n是数组长度k是给定阈值- 空间复杂度O(k)使用一维数组示例验证# 示例1nums [1,2,3,4], k 4# 输出: 6# 示例2nums [3,3,3], k 4# 输出: 0# 示例3nums [6,6], k 2# 输出: 2关键点说明1. 为什么用pow(2, n, MOD)Python内置的快速幂比循环乘2效率更高2. 为什么倒序遍历避免同一个元素被重复使用0-1背包的标准技巧3. 为什么乘以2第一组和k 和 第二组和k 是两种不同的不好分区且当总和≥2k时不会重叠4. 边界情况总和2k时直接返回0避免了后续计算的错误