丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。
有了上面的定义我们就可以知道，丑数的形式就是
所以我们可以定义一个数组，存储第n个丑数。
因为我们要将丑数按从小到大的顺序排序，所以我们就得将对应的丑数放在对应的下标位置，小的放前面。
因为最小的丑数就是1，所以我们初始化dp[0]=1，那么接下来的一个丑数是什么呢？我们自己知道是2。
但是我们能不能有一个格式，去将得到接下来的丑数是谁呢？
这个时候上面我们的出来的丑数的格式就起作用了，丑数的形式无非就是这样
所以我们就将dp[n]去乘以 2、3、5，然后比较出最小的那个，就是我们当前小的那个丑数了。
下面代码实战看注释（自己演示一遍就明白其中的道理）

public int GetUglyNumber_Solution(int index) {
        //1 2 3 4 5 6 8
        if(index <= 6)
            return index;
        int i2 = 0,i3 = 0,i5 = 0;  /*三个指针，记录乘2、3、5的次数*/
        int[] dp = new int[index];  /*存放丑数*/
        dp[0] = 1;  /*第一个丑数是1*/

        for(int i = 1; i < index; i++){
            dp[i] = Math.min(dp[i2]*2,Math.min(dp[i3]*3,dp[i5]*5));  
            /*第一次是 2、3、5比较，得到最小的是2*/
            /*第二次是 4、3、5比较，为什么是4了呢？因为上次2已经乘了一次了，可以放的丑数在4、3、5之间，我们知道是3*/
            if(dp[i] == dp[i2]*2)
                i2++;   /*2被乘了一次了，i2加1*/
            if(dp[i] == dp[i3]*3)
                i3++;  /*3被乘了一次，i3加1*/
            if(dp[i] == dp[i5]*5)
                i5++;
        }
        return dp[index-1];
    }