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];    }