题目链接
题目描述
实现代码
动态规划思想:记dp[i]表示第i个丑数,因为每个位置的丑数跟2,3,5三个数相关,是仅仅由这三个质因数组成的数,写出前十个丑数可以看出,从1开始之后,每个位置的丑数的值都是2,3,5其中一个与前面的某个丑数相乘的结果,因此可以定义三个指针p1/p2/p3分别对应2,3,5相乘的位置,则状态转移方程为:
dp[i] = min(2dp[p1], 3dp[p2], 5*dp[p3])
p1,p2,p3更新条件:min选择到对应的位置;
更新方式:自增1
实现代码:
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n+1];
int p1 = 1;
int p2 = 1;
int p3 = 1;
dp[1] = 1;
for(int i=2; i<=n; i++) {
dp[i] = Math.min(Math.min(2*dp[p1], 3*dp[p2]), 5*dp[p3]);
p1 += (dp[i] == 2*dp[p1] ? 1: 0);
p2 += (dp[i] == 3*dp[p2] ? 1: 0);
p3 += (dp[i] == 5*dp[p3] ? 1: 0);
}
return dp[n];
}
}