丑数系列的题看这一道就可以了
/* 和ugly number2差不多，不过这次的质因子多了，所以用数组来表示质因子的target坐标 target坐标指的是这个质因子此次要乘的前任丑数是谁 */ public int nthSuperUglyNumber(int n, int[] primes) { //记录相乘坐标,存的是每个质因子对应相乘搭档在丑数数组中的下标 int[] target = new int[primes.length]; //动态规划数组 int[] dp = new int[n]; //第一个丑数是0 dp[0] = 1; for (int i = 1; i < n; i++) { //每次都要把所有质因子都乘上对应数试试，维护一个min和一个index int min = Integer.MAX_VALUE; int index = 0; for (int j = 0; j < primes.length; j++) { if (min>primes[j]*dp[target[j]]) { min = primes[j]*dp[target[j]]; index = j; } //别忘了，如果有另外的质因子也组成了相同的数，那么这个质因子的target要跳过 //因为得到相同丑数的组合只保留一种即可 //在丑数2中，由于是分别判断2,3,5，所以重复的组合都跳过了 else if (min==primes[j]*dp[target[j]]) target[j]++; } //更新dp和target dp[i] = min; target[index]++; } return dp[n-1]; }