剑指 Offer 49. 丑数（中等）
题目：
class Solution {
public:
int nthUglyNumber(int n) { //本题思路：dp数组中之前的每一个丑数的三种倍数都要参与新的丑数，直到被选中为止
vector<int> dp(n, 0);
dp[0]=1;
int p2=0, p3=0, p5=0; //三个指针分别维护*2， *3， *5三种情况
for(int i=1;i<n;i++){
dp[i] = min(dp[p2]*2, min(dp[p3]*3, dp[p5]*5));
if(dp[i]==dp[p2]*2) p2++; //指针p2的丑数*2被选中为dp[i]了，下一次*2参与比较的丑数指针为p2++
if(dp[i]==dp[p3]*3) p3++; //不用else if是为了去重，比如6可以是3*2，也可以是2*3得来
if(dp[i]==dp[p5]*5) p5++;
}
return dp[n-1];
}
};
作者：MrSate
链接：https://leetcode.cn/problems/chou-shu-lcof/solutions/263122/chou-shu-ii-qing-xi-de-tui-dao-si-lu-by-mrsate/
来源：力扣（LeetCode）