[数据结构与算法]【LeetCode练习】剑指 Offer 49. 丑数（中等|JS|动态规划）

一、题目描述

二、解题思路

根据定义可知，丑数是前面某个丑数*2或3或5，因此定义p2，p3，p5为前面三个丑数的下标，让其各自乘2、3、5，然后选最小的那个。之后将得到这个丑数的下标+1，下一轮计算就不会再得到这个丑数了。

三、代码实现

var nthUglyNumber = function(n) {
    let dp = new Array(n).fill(0)
    let p2=0,p3=0,p5=0
    dp[0] = 1
    for(let i=1;i<=n;i++){
        ptr2 = dp[p2]*2
        ptr3 = dp[p3]*3
        ptr5 = dp[p5]*5
        dp[i] = Math.min(ptr2,ptr3,ptr5)
        if(dp[i]==ptr2){
            p2++
        }
        if(dp[i]==ptr3){
            p3++
        }
        if(dp[i]==ptr5){
            p5++
        }
    }
    return dp[n-1]
};