题解 | #丑数# | 动态规划解法 | JAVA
丑数
http://www.nowcoder.com/practice/6aa9e04fc3794f68acf8778237ba065b
动态规划解法：
定义数组dp，dp[i]存储第i个丑数，由定义可知，dp[1]=1；
定义三个指针数p2，p3，p5，初始值均初始化为1；
当 2 ≤ i ≤ n时，取dp[i]=min { dp[p2]×p2，dp[p3]×p3，dp[p5]×p5 }；
对于丑数而言，任何丑数都是由2，3，5乘积而成的，即可以通过2，3，5不断构造新的丑数。
i不断递增， 然后找出最小的那个作为新的丑数
/**
* 动态规划解法
*
* @param index
* @return
*/
public int GetUglyNumber_Solution(int index) {
if (index <= 0) {
return 0;
}
int dp[] = new int[index + 1];
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= index; i++) {
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = Math.min(Math.min(num2, num3), num5);
if(dp[i] == num2){
p2++;
}
if(dp[i] == num3){
p3++;
}
if(dp[i] == num5){
p5++;
}
}
return dp[index];
} 
查看10道真题和解析