【月度刷题计划同款】难度不小的 DP 运用

题目描述

这是 LeetCode 上的「1994. 好子集的数目」，难度为「困难」。

Tag : 「状压 DP」

给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个互不相同的质数的乘积，那么我们称它为好子集。

比方说，如果 nums = [1, 2, 3, 4] ：
- [2, 3] ，[1, 2, 3] 和 [1, 3] 是好子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。
- [1, 4] 和 [4] 不是好子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。请你返回 nums 中不同的好子集的数目对
10^9 7
取余的结果。

nums 中的子集是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

示例 1：

代码语言：javascript复制

输入：nums = [1,2,3,4]

输出：6

解释：好子集为：
- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。

示例 2：

代码语言：javascript复制

输入：nums = [4,2,3,15]

输出：5

解释：好子集为：
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。

提示：

1 <= nums.length <= 10^5

1 <= nums[i] <= 30

状压 DP

该问题属于 NP 完全问题，注定不存在多项式解决方案，只能通过「爆搜剪枝」或「状压 DP」来求解。

对子集的乘积进行质数分解，等价于对子集每一位数进行质数分解。

一个显然的突破口是

1 <= nums[i] <= 30

，再加上题目对于「好子集」的定义，我们可以进一步缩减可选数的数量，不超过

的质数个数包括

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

（共

个），将其记作

，在一个好子集中，每个

p[i]

最多出现一次。

同时，题目规定数值相同，下标不同均视为不同方案，因此我们可以先使用数组

cnts

统计在

nums

中每个数的出现次数，

cnts[val] = x

含义为数值

val

在

nums

中的出现次数为

次。

使用的数有限（共

个），并且使用到的数最多出现一次，容易想到使用「状压 DP」来求解：我们使用一个二进制数来表示好子集乘积最终能拆解成哪些质数，如果拆解结果中包含

p[i]

，对应的二进制表示中的第

位则为

，否则为

。

定义

f[state]

为当前子集乘积拆解结果的用到的质数为

state

时的方案数，

state

为一个长度

的二进制数，若

state

中的第

位二进制表示为

，代表数值

p[k]

在拆解结果中出现过；若第

位二进制表示为

代表

p[k]

在拆解结果中没出现过。

我们有起始化条件：空集，即

f[0] = 1

。

不失一般性考虑

f[s]

该如何计算：从前往后考虑每个数值（范围

[2, 30]

的数，

添加与否不对好子集产生影响，最后讨论）是否可以加入到子集中，一个数值

能够添加到子集中的充要条件为题目给定的条件：该数不会被相同的质数相乘表示。

如果一个数值

能够添加到好子集中，我们通过「试除法」将其分解为

中的多个质数，并使用二进制数

cur

来表示用到了

中的哪些质数，然后需要判断

能够添加到那些子集中，其实就是枚举与

cur

无交集的状态

，最终的

f[s]

为「所有合法的

的状态数

f[prev]

」与「数值

的出现次数

cnts[t]

」的乘积之和。

需要注意的是，由于我们是从范围

[2, 30]

范围内从前往后考虑每个

，因此在枚举

时需要进行倒序遍历，确保计算

f[s]

所依赖的

f[prev]

为不考虑当前数值

时的方案数。

由「质数

组成的好子集方案数」为

ans = sum_{state' = 1}^{{1024}} f[state']

，其中

state'

对应一个合法的好子集方案。

在此基础上，再考虑数值

对答案的影响：在每个合法的

state'

前提下，增加若干个

并不影响子集乘积（即好子集增加

后仍为好子集），因此每个合法子集

state'

可以对应出

2^{cnts[1]}

个具体方案（代表每个

即可以选，也可以不选）。

代码：

代码语言：javascript复制

class Solution {
    int MOD = (int)1e9 7;
    int[] p = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int[] cnts = new int[35];
    public int numberOfGoodSubsets(int[] nums) {
        int n = nums.length;
        for (int i : nums) cnts[i]  ;
        int mask = 1 << 10;
        long[] f = new long[mask];
        f[0] = 1;
        for (int i = 2; i <= 30; i  ) {
            if (cnts[i] == 0) continue;
            // 对 i 进行试除
            int cur = 0, x = i;
            boolean ok = true;
            for (int j = 0; j < 10 && ok; j  ) {
                int t = p[j], c = 0;
                while (x % t == 0) {
                    cur |= (1 << j);
                    x /= t; c  ;
                }
                // 如果 i 能够被同一质数试除多次，说明 i 不能加到子集，跳过
                if (c > 1) ok = false;
            }
            if (!ok) continue;
            // 枚举前一状态 prev
            //（确保考虑一个新数值 i 时，依赖的子集 prev 存储的为尚未考虑 i 的方案数）
            for (int prev = mask - 1; prev >= 0; prev--) {
                // 只有当前选择数与前一状态不冲突，则能够进行转移，将方案数进行累加
                if ((prev & cur) != 0) continue;
                f[prev | cur] = (f[prev | cur]   f[prev] * cnts[i]) % MOD;
            }
        }
        long ans = 0;
        // 统计所有非空集的方案数
        for (int i = 1; i < mask; i  ) ans = (ans   f[i]) % MOD;
        // 在此基础上，考虑每个 1 选择与否对答案的影响
        for (int i = 0; i < cnts[1]; i  ) ans = ans * 2 % MOD;
        return (int) ans;
    }
}

时间复杂度：预处理每个数值的出现次数复杂度为

O(n)

；令数值范围

C = 30

，状态数为

M = 1024

，DP 部分复杂度为

O(C times M)

。整体复杂度为

O(n C times M)

空间复杂度：

O(C M)

关于「倒序遍历」状态的答疑

上述的分析推理基于我们进行了「一维空间优化」。

原始的状态定义应该是

f[i][state]

为考虑范围在

[1,30]

的前

个数，并且好子集拆解结果的用到的质数为

state

时的方案数。

我们有显然的初始化条件：

f[1][0] = 1

，代表当只有数值

的话，只有空集为合法方案。

不失一般性的考虑

f[i][s]

该如何计算，根据使用数值

来进行分情况讨论：

不考虑数值

（或是数值

在

nums

中没有出现，无法考虑），则有

f[i][s] = f[i - 1][s]

；

考虑数值

，分析方法同「一维空间优化」，对数值

应用「试除法」拆解成对应的质数状态

cur

，然后找到可以转移的前一状态

来尝试转移，则有

f[i][cur | prev] = f[i][cur | prev] f[i - 1][prev]

。

基于对「原始状态定义」的分析，我们发现

f[i][cur | prev]

的更新（累加）依赖于

f[i][prev]

，同时

是

cur | prev

的子集，因此在进行「一维空间优化」，我们需要确保所依赖的状态没有被覆盖更新，即采用「倒序遍历」。

代码：

代码语言：javascript复制

class Solution {
    int MOD = (int)1e9 7;
    int[] p = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int[] cnts = new int[35];
    public int numberOfGoodSubsets(int[] nums) {
        for (int i : nums) cnts[i]  ;
        int mask = 1 << 10;
        long[][] f = new long[35][mask];
        f[1][0] = 1;
        for (int i = 2; i <= 30; i  ) {
            for (int s = 0; s < mask; s  ) f[i][s] = f[i - 1][s];
            if (cnts[i] == 0) continue;
            int cur = 0, x = i;
            boolean ok = true;
            for (int j = 0; j < 10 && ok; j  ) {
                int t = p[j], c = 0;
                while (x % t == 0) {
                    cur |= (1 << j);
                    x /= t; c  ;
                }
                if (c > 1) ok = false;
            }
            if (!ok) continue;
            for (int prev = 0; prev < mask; prev  ) {
                if ((prev & cur) != 0) continue;
                f[i][prev | cur] = (f[i][prev | cur]   f[i - 1][prev] * cnts[i]) % MOD;
            }
        }
        long ans = 0;
        for (int i = 1; i < mask; i  ) ans = (ans   f[30][i]) % MOD;
        for (int i = 0; i < cnts[1]; i  ) ans = ans * 2 % MOD;
        return (int) ans;
    }
}

时间复杂度：预处理每个数值的出现次数复杂度为

O(n)

；令数值范围

C = 30

，状态数为

M = 1024

，DP 部分复杂度为

O(C times M)

。整体复杂度为

O(n C times M)

空间复杂度：

O(C times M)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1994 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

dp int 遍历二进制数组

0 人点赞