1.题目基本信息

1.1.题目描述

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。

给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。

题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

1.2.题目地址

https://leetcode.cn/problems/super-ugly-number/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，构建维护变量。points[j]维护primes[j]质数对应的一个在dp中的指针，该指针保证丑数dp[points[j]]*primes[i]在下一轮质数选择的候选者序列中

第二步，状态定义。dp[i]为第i个丑数

第三步，状态初始化。dp[1]=1

第四步，状态转移。dp[i]=min(dp[points[j]]primes[j] for j in range(len(primes)))。在选择到最小候选丑数dp[points[j]]j后，都需要自增points[j]，将下一个质数j对应的候选丑数加到候选者序列中。

第五步，dp[n]即为题解

3.解题代码

python代码

class Solution:
    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
        # 思路：动态规划
        # 第一步，构建维护变量。points[j]维护primes[j]质数对应的一个在dp中的指针，该指针保证丑数dp[points[j]]*primes[i]在下一轮质数选择的候选者序列中
        m = len(primes)
        points = [1] * m
        # 第二步，状态定义。dp[i]为第i个丑数
        dp = [0] * (n + 1)
        # 第三步，状态初始化。dp[1]=1
        dp[1] = 1
        # 第四步，状态转移。dp[i]=min(dp[points[j]]*primes[j] for j in range(len(primes)))。在选择到最小候选丑数dp[points[j]]*j后，都需要自增points[j]，将下一个质数j对应的候选丑数加到候选者序列中。
        for i in range(2, n + 1):
            nums = [dp[points[j]] * primes[j] for j in range(m)]
            dp[i] = min(nums)
            for j, num in enumerate(nums):
                if dp[i] == num:
                    points[j] += 1
        # 第五步，dp[n]即为题解
        return dp[n]

4.执行结果