【月度刷题计划同款】难度不小的 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
中不同的 好 子集的数目对 109+710^9 + 7109+7 取余 的结果。
nums
中的 子集 是通过删除 nums
中一些(可能一个都不删除,也可能全部都删除)元素后剩余元素组成的数组。如果两个子集删除的下标不同,那么它们被视为不同的子集。
示例 1:
输入: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:
输入: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<=1051 <= nums.length <= 10^51<=nums.length<=105
- 1<=nums[i]<=301 <= nums[i] <= 301<=nums[i]<=30
状压 DP
该问题属于 NP 完全问题,注定不存在多项式解决方案,只能通过「爆搜 + 剪枝」或「状压 DP」来求解。
对子集的乘积进行质数分解,等价于对子集每一位数进行质数分解。
一个显然的突破口是 1<=nums[i]<=301 <= nums[i] <= 301<=nums[i]<=30,再加上题目对于「好子集」的定义,我们可以进一步缩减可选数的数量,不超过 303030 的质数个数包括 [2,3,5,7,11,13,17,19,23,29][2, 3, 5, 7, 11, 13, 17, 19, 23, 29][2,3,5,7,11,13,17,19,23,29](共 101010 个),将其记作 ppp,在一个好子集中,每个 p[i]p[i]p[i] 最多出现一次。
同时,题目规定数值相同,下标不同均视为不同方案,因此我们可以先使用数组 cntscntscnts 统计在 numsnumsnums 中每个数的出现次数,cnts[val]=xcnts[val] = xcnts[val]=x 含义为数值 valvalval 在 numsnumsnums 中的出现次数为 xxx 次。
使用的数有限(共 101010 个),并且使用到的数最多出现一次,容易想到使用「状压 DP」来求解:我们使用一个二进制数来表示好子集乘积最终能拆解成哪些质数,如果拆解结果中包含 p[i]p[i]p[i],对应的二进制表示中的第 iii 位则为 111,否则为 000。
定义 f[state]f[state]f[state] 为当前子集乘积拆解结果的用到的质数为 statestatestate 时的方案数,statestatestate 为一个长度 101010 的二进制数,若 statestatestate 中的第 kkk 位二进制表示为 111,代表数值 p[k]p[k]p[k] 在拆解结果中出现过;若第 kkk 位二进制表示为 000 代表 p[k]p[k]p[k] 在拆解结果中没出现过。
我们有起始化条件:空集,即 f[0]=1f[0] = 1f[0]=1。
不失一般性考虑 f[s]f[s]f[s] 该如何计算:从前往后考虑每个数值(范围 [2,30][2, 30][2,30] 的数,111 添加与否不对好子集产生影响,最后讨论)是否可以加入到子集中,一个数值 ttt 能够添加到子集中的充要条件为题目给定的条件:该数不会被相同的质数相乘表示。
如果一个数值 ttt 能够添加到好子集中,我们通过「试除法」将其分解为 ppp 中的多个质数,并使用二进制数 curcurcur 来表示用到了 ppp 中的哪些质数,然后需要判断 ttt 能够添加到那些子集中,其实就是枚举与 curcurcur 无交集的状态 prevprevprev,最终的 f[s]f[s]f[s] 为「所有合法的 prevprevprev 的状态数 f[prev]f[prev]f[prev]」与「数值 ttt 的出现次数 cnts[t]cnts[t]cnts[t] 」的乘积之和。
需要注意的是,由于我们是从范围 [2,30][2, 30][2,30] 范围内从前往后考虑每个 ttt,因此在枚举 prevprevprev 时需要进行倒序遍历,确保计算 f[s]f[s]f[s] 所依赖的 f[prev]f[prev]f[prev] 为不考虑当前数值 ttt 时的方案数。
由「质数 ppp 组成的好子集方案数」为 ans=∑state′=11024f[state′]ans = \sum_{state' = 1}^{{1024}} f[state']ans=∑state′=11024f[state′],其中 state′state'state′ 对应一个合法的好子集方案。
在此基础上,再考虑数值 111 对答案的影响:在每个合法的 state′state'state′ 前提下,增加若干个 111 并不影响子集乘积(即好子集增加 111 后仍为好子集),因此每个合法子集 state′state'state′ 可以对应出 2cnts[1]2^{cnts[1]}2cnts[1] 个具体方案(代表每个 111 即可以选,也可以不选)。
代码:
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)O(n)O(n);令数值范围 C=30C = 30C=30,状态数为 M=1024M = 1024M=1024,DP 部分复杂度为 O(C×M)O(C \times M)O(C×M)。整体复杂度为 O(n+C×M)O(n + C \times M)O(n+C×M)
- 空间复杂度:O(C+M)O(C + M)O(C+M)
关于「倒序遍历」状态的答疑
上述的分析推理基于我们进行了「一维空间优化」。
原始的状态定义应该是 f[i][state]f[i][state]f[i][state] 为考虑范围在 [1,30][1,30][1,30] 的前 iii 个数,并且好子集拆解结果的用到的质数为 statestatestate 时的方案数。
我们有显然的初始化条件:f[1][0]=1f[1][0] = 1f[1][0]=1,代表当只有数值 111 的话,只有空集为合法方案。
不失一般性的考虑 f[i][s]f[i][s]f[i][s] 该如何计算,根据使用数值 iii 来进行分情况讨论:
- 不考虑数值 iii(或是数值 iii 在 numsnumsnums 中没有出现,无法考虑),则有 f[i][s]=f[i−1][s]f[i][s] = f[i - 1][s]f[i][s]=f[i−1][s];
- 考虑数值 iii,分析方法同「一维空间优化」,对数值 iii 应用「试除法」拆解成对应的质数状态 curcurcur,然后找到可以转移的前一状态 prevprevprev 来尝试转移,则有 f[i][cur∣prev]=f[i][cur∣prev]+f[i−1][prev]f[i][cur | prev] = f[i][cur | prev] + f[i - 1][prev]f[i][cur∣prev]=f[i][cur∣prev]+f[i−1][prev]。
基于对「原始状态定义」的分析,我们发现 f[i][cur∣prev]f[i][cur | prev]f[i][cur∣prev] 的更新(累加)依赖于 f[i][prev]f[i][prev]f[i][prev],同时 prevprevprev 是 cur∣prevcur | prevcur∣prev 的子集,因此在进行「一维空间优化」,我们需要确保所依赖的状态没有被覆盖更新,即采用「倒序遍历」。
代码:
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)O(n)O(n);令数值范围 C=30C = 30C=30,状态数为 M=1024M = 1024M=1024,DP 部分复杂度为 O(C×M)O(C \times M)O(C×M)。整体复杂度为 O(n+C×M)O(n + C \times M)O(n+C×M)
- 空间复杂度:O(C×M)O(C \times M)O(C×M)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1994
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
转载自:https://juejin.cn/post/7256307512244535352