剑指 Offer 49. 丑数

题目链接： 剑指 Offer 49. 丑数

题目描述：

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

解法思路：

代码：

// dp[i] 代表第 i 个丑数
// 维护三个索引，不断乘 2 3 5，谁小当前 dp[i] 选谁
func nthUglyNumber(n int) int {
    
    i2, i3, i5 := 1, 1, 1
    dp := make([]int,n+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 dp[i] == v2 {
            i2++
        }
        if dp[i] == v3 {
            i3++
        }
        if dp[i] == v5 {
            i5++
        }
    }
    return dp[n] 

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