2518.好分区的数目

链接：2518.好分区的数目
难度：Hard
标签：数组、动态规划
简介：返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。

题解 1 - cpp

• 编辑时间：2022-12-25
• 执行用时：112ms
• 内存消耗：36.7MB
• 编程语言：cpp
• 解法介绍：逆向统计，统计出有多少组是少于 k 的，res = sum - 2 * val。

class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        if (accumulate(nums.begin(), nums.end(), 0LL) < 2 * k) return 0;
        sort(nums.begin(), nums.end());
        int n = nums.size(), mod = 1e9 + 7, ans = 1;
        vector<vector<int>> dp(n + 1, vector<int>(k, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            ans = (ans * 2) % mod;
            dp[i][0] = 1;
            for (int j = 1; j < k; j++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
                if (j >= nums[i - 1]) dp[i][j] = (dp[i][j] + dp[i - 1][j - nums[i - 1]]) % mod;
            }
        }
        for (auto &num : dp[n]) ans = (ans - 2 * num % mod + mod) % mod;
        return ans;
    }
};