编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最开始用暴力法超时
class Solution {
public boolean isUgly(int n)
{
if (n<=0)
return false;
while(n%2 ==0)
n/=2;
while(n%3 ==0)
n/=3;
while(n%5 ==0)
n/=5;
return n==1;
}
public int nthUglyNumber(int n) {
int i=1;
int count=0;
while(count<n)
{
while(isUgly(i))
{
count++;
}
i++;
}
return i-1;
}
}没想出来怎么优化，看了题解之后发现是用动态规划+三指针，利用之前的计算从而减少计算量。
dp保存按序排列的丑数，三指针分别是*2，*3，*5，找出下一个丑数。
引用另一个人“复习备考的龙龙”的解释：
1.采用动态规划思想，假设要找下标i对应的丑数dp[i],可以用i之前的所有丑数乘若干个2直到大于上一个丑数dp[i-1]，记此数为num1;同理用i之前的所有丑数乘若干个3直到大于上一个丑数dp[i-1]，记此数为num2；用i之前的所有丑数乘若干个5直到大于上一个丑数dp[i-1]，记此数为num3。这三个数中的最小数字就是第i个丑数dp[i]。
2.但是呢，其实没必要把i之前的所有丑数乘2或者乘3或者乘5。**在i之前的丑数中，肯定存在一个丑数（下标记为index2），乘2以后正好大于i的上一个丑数dp[i-1],index2之前的丑数乘2都小于等于dp[i-1]**;我们只需要记录index2，每次直接用这个下标对应的数乘2就行，并且在下标不满足时更新下标。同理我们也要记录乘3和乘5对应的下标。
第一点好理解，第二点的意思是对于*2指针，只用记录*2后刚好大于dp[i-1]的下标i2，*3、*5指针同理。这样dp[i]即为num1、num2、num3中的最小值乘以相对应的指针值，dp[i]即为dp[n-1]的值。
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
for (int i = 1; i < n; i++) {
int min = Math.min(dp[i2] * 2, Math.min(dp[i3] * 3, dp[i5] * 5));
if (min == dp[i2] * 2) i2++;
if (min == dp[i3] * 3) i3++;
if (min == dp[i5] * 5) i5++;
dp[i] = min;
}
return dp[n - 1];
}
作者：pphdsny
链接：https://leetcode-cn.com/problems/ugly-number-ii/solution/javati-jie-dong-tai-gui-hua-san-zhi-zhen-by-pphdsn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。