264. Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

本题使用DP方法来做的，看了答案才了解，状态方程不是很好想，思路是做三个索引，分别表示2的倍数，3的倍数和5的倍数，然后再做三个factor值，分别记录*2，*3，*5；min为factor三个值的最小值，然后判断这个最小值是哪个factor的，将那个factor=对应的倍数*索引值的数组值，代码如下：

 1 public class Solution {
 2     public int nthUglyNumber(int n) {
 3         int[] num = new int[n];
 4         int index2 = 0,index3 = 0,index5 = 0;
 5         int factor2 = 2,factor3 = 3,factor5 = 5;
 6         num[0] = 1;
 7         for(int i=1;i<n;i++){
 8             int min = Math.min(Math.min(factor2,factor3),factor5);
 9             num[i]  =min;
10             if(min==factor2){
11                 factor2 = 2*num[++index2];
12             }
13             if(min==factor3){
14                 factor3 = 3*num[++index3];
15             }
16             if(min==factor5){
17                 factor5 = 5*num[++index5];
18             } 
19         }
20         return num[n-1];
21     }
22 }