?LeetCode刷題實戰(zhàn)264：丑數(shù) II

示例 1：

輸入：n = 10
輸出：12
解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個丑數(shù)組成的序列。

示例 2：

輸入：n = 1
輸出：1
解釋：1 通常被視為丑數(shù)。

def nthUglyNumber(n):
    dp = [0] * n
    #第一個丑數(shù)為1
    dp[0] = 1
    #表示下一個丑數(shù)是乘以哪個質(zhì)因子（2，3，5）得到的。
    #p2表示乘以2，p3表示乘以3， p5表示乘以5.
    p2 = 0
    p3 = 0
    p5 = 0
    #遍歷
    for i in range(1, n):
        dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)
        #更新對應(yīng)的指針
        if dp[i] == dp[p2] * 2:
            p2 += 1
        if dp[i] == dp[p3] * 3:
            p3 += 1
        if dp[i] == dp[p5] * 5:
            p5 += 1
    print(dp)
    return dp[-1]