丑数

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

思路：

因为丑数只包含质因子2、3、5，所以第n个丑数，必由第i个丑数乘以2或3或5得来，1<=i<n,而对于乘以2、乘以3和乘以5的i可能不一样。设index2表示乘以2的下标，index3表示乘以3的下标，index5表示乘以5的下标。dp[i]表示第i个丑数，则dp[i]=min(min(dp[index2]*2,dp[index3]*3),dp[index5]*5)，初始时,index2=1,index3=1,index5=1。如果dp[i]==dp[index2]*2,则index2加一,index3和index5也一样。

代码：

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n+1);
        dp[1] = 1;
        int index2 = 1;
        int index3 = 1;
        int index5 = 1;
        for(int i = 2;i <= n;i++) {
            dp[i] = min(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];
    }
};