【DP】超级丑数

题源

非常神奇的动态规划，不要一直尝试枚举所有的乘积，或者卡在primes数组中

定义数组 dp，其中 \(dp[i]\) 表示第 \(i\) 个超级丑数，第 \(n\) 个超级丑数即为 \(dp[n]\)。

由于最小的超级丑数是 1，因此 \(dp[1]=1\)。

如何得到其余的超级丑数呢？创建与数组 \(primes\) 相同长度的数组 \(pointers\)，表示下一个超级丑数是当前指针指向的超级丑数乘以对应的质因数。初始时，数组 \(pointers\) 的元素值都是 \(1\)。

当 \(2≤i≤n\) 时，令 \(dp[i]=min⁡{dp[pointers[j]]×primes[j]\)，然后对于每个 \(0≤j<m\)，分别比较 \(dp[i]\) 和 \(dp[pointers[j]]×primes[j]\) 是否相等，如果相等则将 \(pointers[j]\) 加 \(1\)。

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        dp = [0] * (n + 1)
        m = len(primes)
        pointers = [0] * m
        nums = [1] * m

        for i in range(1, n + 1):
            min_num = min(nums)
            dp[i] = min_num
            for j in range(m):
                if nums[j] == min_num:
                    pointers[j] += 1
                    nums[j] = dp[pointers[j]] * primes[j]
        return dp[n]