原题：https://leetcode-cn.com/problems/chou-shu-lcof/

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

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

1 是丑数。
n 不超过1690。

---

由题意得，每个丑数之间必然有2、3、5倍数的关系，故而有解：动态规划；（此外也可以用有序序列合并的方法）

显而易见的是，dp[i]必然是dp[a](a<i)的2、3、5倍数，唯一的难点就是在于排序问题，例如5*2>2*3，故而每个倍数需要分别讨论；

现在初始化变量a，b，c分别表示已经被2、3、5所乘的数的索引；

a=n即表示数组中已经有前n个数被2乘，以此类推；

先设定dp[0]=1，a=0，b=0，c=0；

接下来比较三个数dp[a]*2、dp[b]*3、dp[c]*5，取得三者中最小的数，再令其索引+1；

例如三者中dp[a]*2最小，则令a++；

时间复杂度O(n)；

代码：

int nthUglyNumber(int n) {
     int a = 0, b = 0, c = 0;
     int* dp = new int[n];
     dp[0] = 1;
     for (int i = 1; i < n; i++)
     {
         int x = dp[a] * 2, y = dp[b] * 3, z = dp[c] * 5;
         dp[i] = min(min(x, y), z);
         if (dp[i] == x) a++;
         if (dp[i] == y) b++;
         if (dp[i] == z) c++;
     }
     return dp[n-1];
 }