# 264. Ugly Number II

[Link](https://leetcode.com/problems/ugly-number-ii/)

**Solution**

當下的ugly number一定是之前某次的值\* 2 or \*3 or \*4

保持三個指標，indexTimes2, indexTimes3, indexTimes5, 分別指向前面該位置的元素，並分別乘上2 3 5當candidates。

```java
 dp[i] = Math.min(dp[indexToTimes2] * 2, 
                  Math.min(dp[indexToTimes3] * 3, dp[indexToTimes5] * 5));
```

每次就比較哪個candidate所造成的ugly number最小 ，並增加index若他產生的值被採納。

```java
 public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int indexToTimes2 = 0, indexToTimes3 = 0, indexToTimes5 = 0;
        for(int i = 1; i < n ; i++){
            dp[i] = Math.min(dp[indexToTimes2] * 2, Math.min(dp[indexToTimes3] * 3, dp[indexToTimes5] * 5));
            if(dp[i] == (dp[indexToTimes2]*2)) indexToTimes2++; 
            //dp[indexToTimes2]*2 num is used this time, increase indexToTimes2
            if(dp[i] == (dp[indexToTimes3]*3)) indexToTimes3++;
            //dp[indexToTimes3]*3 num is used this time, increase indexToTimes3
            if(dp[i] == (dp[indexToTimes5]*5)) indexToTimes5++;
            //dp[indexToTimes5]*5 num is used this time, increase indexToTimes5
        }
        return dp[n-1];
    }
```
