264. Ugly Number II

Link

Solution

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

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

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

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

 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];
    }