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

思路：

一開始，我考慮的是遍歷查找，逐個判斷是否為丑數(shù)，果斷耗時(shí)太長。

//TLE,1600th cost 17.148s	public static int nthUglyNumber(int n){		if(n <= 0){			return 0;		}		int count = 0; //記錄丑數(shù)的個數(shù)		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;	}之后我在網(wǎng)上查找學(xué)習(xí)下，這里需要用到動態(tài)規(guī)劃的思想。
動態(tài)規(guī)劃的基本思想：若要解一個給定的問題，我們需要解不同部分（即子問題），再合并子問題的解以得出原問題的解。
通過上面這句話，我們可以發(fā)現(xiàn)動態(tài)規(guī)劃主要用于解決重疊子問題和優(yōu)化子結(jié)構(gòu)，比如最典型的斐波那契數(shù)列。
好的，再回到我們這道題目，那么我們應(yīng)該專注于尋找所有由2，3，5因子組成的數(shù)字，這個思想和計(jì)算n以內(nèi)素?cái)?shù)個數(shù)中的Sieve of Eratosthenes思想很是相近，只不過這道題是找到丑數(shù)然后添加進(jìn)數(shù)組，而CountPrimers是找到非素?cái)?shù)去除掉。那么我們需要將２，３，５的使用次數(shù)和對應(yīng)的操作丑數(shù)均可用同一指針來記錄。然后對之前記錄的丑數(shù)逐個乘以這３個因子。
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];    }