49. 丑数.md

解题思路

动态规划

dp[i] 代表第 i 个丑数

维护三个索引，不断乘 2 3 5，谁小当前 dp[i] 选谁

func nthUglyNumber(n int) int {
    dp := make([]int, n+1)
    i2, i3, i5 := 1, 1, 1
    dp[1] = 1
    for i := 2; i <= n; i++ {
        v2, v3, v5 := dp[i2] * 2, dp[i3] * 3, dp[i5] * 5
        dp[i] = min(v2, min(v3, v5))
        if v2 == dp[i] {
            i2++
        }
        if v3 == dp[i] {
            i3++
        }
        if v5 == dp[i] {
            i5++
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}