264. Ugly Number II

An ugly number must be multiplied by 2, 3 or 5 from a smaller ugly number.

For example,
1 --> 2, 3, 5
2 --> 4, 6, 10
3 --> 6, 9, 15

From the example above, we see that there are three lists as columns. All we need to do is to merge the three lists. Let dp[i] be the ith ugly number. We keep three pointers for each list and only move the pointer when the element in the list has been merged into the result. Therefore, dp[i] = min(2*dp[p2], 3*dp[p3], 5*dp[p5]), and move p(2/3/5) to next when 2*dp[p(2/3/5)] has been chosen as dp[i].

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