leetcode264 Ugly Number II

思路：

新生成的数字一定是原来的某个数字乘以2、3或5，为了得到最小的一个，需要用三个指针记录原数字的位置以供比较。为了避免重复，生成新数字以后，原数字对应的指针需要后移一下。

实现：

 1 class Solution 
 2 {
 3 public:
 4     int nthUglyNumber(int n) 
 5     {
 6         vector<int> dp(n);
 7         dp[0] = 1;
 8         int p2 = 0, p3 = 0, p5 = 0;
 9         for (int i = 1; i < n; i++)
10         {
11             dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5));
12             if (dp[i] == dp[p2] * 2) p2++;
13             if (dp[i] == dp[p3] * 3) p3++;
14             if (dp[i] == dp[p5] * 5) p5++;
15         }
16         return dp[n - 1];
17     }
18 };