编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:  

1 是丑数。
n 不超过1690。

 

 

思路：

动态规划的思想  第n个丑数是怎么来的？它一定是在第n个丑数之前的n-1个丑数中的一个，乘以2、3、5得来的。
现在的问题就是，如何从前n-1个丑数中选出那个丑数来，然后又如何确定是乘以2还是3 或者是5

用变量two   three  five同时指向dp[]中出现的第一个丑数  这个丑数乘以2 大于dp[]中最后一个丑数。 此时，很显然two * 2就是下一个丑数的备选值，同理选出three * 3、five * 5，然后从这三个值里面选择最小的作为下一个丑数。以此类推

    public int nthUglyNumber(int n) {
		int two=0,three=0,five=0;  //代表存放2  3  5三种数字
	        int[] dp = new int[n];
	        dp[0] = 1;
	        for(int i = 1; i < n; i++) {
	        	//每一个丑数  都是由前面的丑数乘以 2 ， 3 ， 5得到
	            int a = dp[two] * 2;
	            int b = dp[three] * 3;
	            int c = dp[five] * 5;
	            int min = Math.min(a, Math.min(b, c));
	            if(a == min) two++;   //更新位置
	            if(b == min) three++;
	            if(c == min) five++;
	            dp[i] = min;
	        }
	        return dp[n-1];
	  }