26.Ugly Number2

Write a PRogram to find the n-th ugly number.

思路：

一开始，我考虑的是遍历查找，逐个判断是否为丑数，果断耗时太长。

//TLE,1600th cost 17.148s	public static int nthUglyNumber(int n){		if(n <= 0){			return 0;		}		int count = 0; //记录丑数的个数		int temp = 0;		for (int i = 1; count < n; i++) {			temp = i;			int num2 = temp % 2;			int num3 = temp % 3;			int num5 = temp % 5;			while(num2 == 0||num3 == 0||num5 == 0){				if(num2 == 0){					temp = temp/2;				}				else if(num3 == 0){					temp = temp/3;				}				else{					temp = temp/5;				}				num2 = temp % 2;				num3 = temp % 3;				num5 = temp % 5;			}			if(temp == 1){				count++;			}			if(count == n){				temp = i;			}		}		return temp;	}之后我在网上查找学习下，这里需要用到动态规划的思想。
动态规划的基本思想：若要解一个给定的问题，我们需要解不同部分（即子问题），再合并子问题的解以得出原问题的解。
通过上面这句话，我们可以发现动态规划主要用于解决重叠子问题和优化子结构，比如最典型的斐波那契数列。
好的，再回到我们这道题目，那么我们应该专注于寻找所有由2，3，5因子组成的数字，这个思想和计算n以内素数个数中的Sieve of Eratosthenes思想很是相近，只不过这道题是找到丑数然后添加进数组，而CountPrimers是找到非素数去除掉。那么我们需要将２，３，５的使用次数和对应的操作丑数均可用同一指针来记录。然后对之前记录的丑数逐个乘以这３个因子。
public static int nthUglyNumber2(int n) {  		if(n == 0)			return 0;		if(n == 1)			return 1;		int[] dp = new int[n];		dp[0] = 1;		int index2 = 0;		int index3 = 0;		int index5 = 0;		for (int i = 1; i < n; i++) {			dp[i] = Math.min(Math.min(dp[index2]*2, dp[index3]*3),dp[index5]*5);			if(dp[i] == dp[index2]*2){				index2++;			}			if(dp[i] == dp[index3]*3){				index3++;			}			if(dp[i] == dp[index5]*5){				index5++;			}		}		return dp[n-1];    }