Sword finger offer 49. ugly number

subject

We will include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）. Seek the order from small to large n Ugly number .

Example :

 Input : n = 10
 Output : 12

explain : 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 Before 10 Ugly number .

explain :
1 It's ugly .
n No more than 1690.

Ideas

• Dynamic programming
• 2,3,5 Multiple in , The smallest one now

Program

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [1] * n
        a,b,c=0,0,0
        for i in range(1,n):
            n2 = dp[a] * 2
            n3 = dp[b] * 3
            n5 = dp[c] * 5
            dp[i] = min(n2,n3,n5)
            if dp[i] ==n2: a = a+ 1
            if dp[i] ==n3: b = b+ 1
            if dp[i] ==n5: c = c+ 1
        return dp[-1]