264 丑数II

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

解法

• 动态规划

class Solution:
    def nthUglyNumber(self, num: int) -> int:
        dp = [0]*num
        dp[0] = 1
        l2,l3,l5 = 0,0,0
        for i in range(1,num):
            dp[i] = min(2*dp[l2],3*dp[l3],5*dp[l5])

            if dp[i] == 2*dp[l2]:
                l2 += 1
            if dp[i] == 3*dp[l3]:
                l3 += 1
            if dp[i] == 5*dp[l5]:
                l5 += 1
        return dp[-1]