leetcode 剑指offer49：丑数

题目描述：
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
思路： 动态规划
状态定义： dp[n]即第n个丑数
状态转移：因为是只含有质因子，所以可以看成：后面的数是前面的数乘以2或3或5得到的，所以我们需要三个标记位或者称为是指针，来记录*2，*3， *5操作具体到哪个数了，每次取当前位置进行操作后的三个数中的最小的一个，然后改变标记位置即可，主要参考的题解链接

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        a, b, c = 0, 0, 0
        # a, b, c 表示三个指针，指针所指向的位置可以分别继续通过
        # 乘*2， *3， *5构成丑数，每次取他们构成之后的最小值，然后指针向后移动一位
        dp = [1 for _ in range(n)]
        dp[0] = 1
        for i in range(1, n):
            dp[i] = min(dp[a] * 2, dp[b] * 3, dp[c] * 5)
            if dp[i] == dp[a] * 2: a += 1
            if dp[i] == dp[b] * 3: b += 1
            if dp[i] == dp[c] * 5: c += 1
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13