264.Ugly Number II

1-DP-MergeSort

http://www.cnblogs.com/grandyang/p/4743837.html

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