動態規劃解決。

關鍵是理解如何生成新的丑數。這道題和經典的斐波那契數列問題其實是一樣的。求第n個數，需要用第n個數前面的數來求。不同的是，斐波那契數列不會重復。而本題的丑數，會重復出現。

class Solution {
public:int nthUglyNumber(int n) {//dp[i]表示第i個丑數，dp[0]無意義vector<int> dp(n+1);dp[1] = 1;int p2 = 1;int p3 = 1;int p5 = 1;int num2,num3,num5;for(int i = 2;i <=n;i++){num2 = dp[p2]*2;num3 = dp[p3]*3;num5 = dp[p5]*5;dp[i] = min(min(num2,num3),num5);if(dp[i] == num2) p2++;if(dp[i] == num3) p3++;if(dp[i] == num5) p5++;}return dp[n];}
};