Jane Street的一道DP解题

Doomed-Yue 发表于 2023-7-6 07:52
想问一下既然是subset，暴力backtracking是不是也可以，就是复杂度有点高

backtrack的复杂度过高，leetcode的内容nums长度一般可以到10**3，backtrack绝对会超时。

337845818 发表于 2023-7-6 07:46
数组中有0还需要考虑吗

当target不为0，而数组中有0时，背包问题中这个0仅仅是“不包含这个0”的情况，即直接跳过这个0，这种情况下0不需要考虑。但是当target就是0时，数组中的0肯定需要被考虑，而且不管有几个0都会被考虑

K的因数的数量是有限的,在K<1e9时不超过2000个 （查一下highly composite number)

DP[position][K的因子] =到这个位置为止积为这个因子的集合个数
对n=300000这一数量级应该没有问题的

JS不会问这种题
你看错了巴?