题目描述

编写程序找第 n 个丑数。

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

例如， 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 就是前10个丑数。

注意:

1 一般也被当做丑数
n不超过1690

最优解法——DP（AC）

假设我们现在已经有了一个丑数的有序数组，如果要找到下一个丑数，则可以将数组中的每一个数乘以2，并将其中第一个大于当前丑数的的结果记为M2，同样将当前有序数组每一个数都乘以3，第一个大于当前丑数的的结果记为M3，同样方式得到乘以5的第一个大于当前丑数的结果记为M5。可以下一个丑数必然是min(M2, M3, M5)。
事实上我们并不必要将数组中的每个数都乘以2,3,5。对于乘以2来说，我们只要找到第一个乘以2大于当前丑数的数在数组中的位置，同样找到第一个乘以3,5大于当前丑数的数的位置。如果当前丑数记为M，然后就可以使用min(M2, M3, M*5)来产生下一个丑数。
更好的讲解：https://www.cnblogs.com/liujinhong/p/6020220.html
复杂度O(n)
Beat 18%

class Solution:
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * 1700
        dp[1] = 1
        
        last_two = 1
        last_three = 1
        last_five = 1
        
        for i in range(2,n + 1):
            dp[i] = min(min(dp[last_two] * 2,dp[last_three] * 3),dp[last_five] * 5)
            if(dp[i] == dp[last_two] * 2):
                last_two += 1
            if(dp[i] == dp[last_three] * 3): # 注意这里，可能有dp[last_two] * 2 == dp[last_three] * 3的情况出现
                last_three += 1
            if(dp[i] == dp[last_five] * 5):
                last_five += 1

            # print(str(last_two) + str(last_three) + str(last_five))
        return dp[n]