264. 丑数 II

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

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

1 是丑数。
n 不超过1690。

本题一开始思路是，每个丑数都是通过之前的丑数乘以2，乘以3，乘以5而得到的，而第一个丑数是1，是不是可以用动态规划的思想去做本题呢。
确实是可以的，我们basement就是第一个数字是1的时候，然后在此基础上我们乘2,3,5看看哪个数是最小的，我们就要取最小的。那每次都是这么做吗，显然不可能是这样的，如果这么做，我们每次都会乘2，因此我们这个动归不是基于之前一个数的公式，而是应该基于3个指针。
我们可以初始化3个指针i2,i3,i5初始指向1，当i2 i3 i5分别乘2,3,5哪个数最小，就是取哪个数当做之后的数，之后就可以把指针往后移动，这样就可以解决之前的问题了，答案也就出来。
本题其实是需要一点灵感和动归思想去解决的，如果第一次没做出来也没事，只要第二次看见本题或者类似题目能够想得到这种方法即可。
代码如下:

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int [n];
        
        dp[0] = 1;
        int i2 = 0, i3 = 0, i5 = 0;
        
        for(int i = 1; i < n; i++){
            int ugly = Math.min(Math.min(dp[i2] * 2 ,dp[i3] * 3),dp[i5] * 5);
            dp[i] = ugly;

            if(ugly == dp[i2] * 2) i2++;
            if(ugly == dp[i3] * 3) i3++;
            if(ugly == dp[i5] * 5) i5++;
        }
        return dp[n-1];
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。