LeetCode-313. Super Ugly Number [C++][Java]

313. Super Ugly Numberhttps://leetcode.com/problems/super-ugly-number/

A super ugly number is a positive integer whose prime factors are in the array primes.

Given an integer n and an array of integers primes, return the nth super ugly number.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

Constraints:

• 1 <= n <= 106
• 1 <= primes.length <= 100
• 2 <= primes[i] <= 1000
• primes[i] is guaranteed to be a prime number.
• All the values of primes are unique and sorted in ascending order.

class Solution {
public:
    int nthSuperUglyNumber(int n, vector& primes) {
        int i, j, k = primes.size();
    	vector idx(k,1);
        vector dp(n+1, LONG_LONG_MAX);
        dp[1] = 1;
    	for (i = 2; i <= n; ++i) {	
	    	for (j = 0; j < k; ++j) {
                long long tmp = dp[idx[j]]*primes[j];
                if (tmp < dp[i]) {dp[i] = tmp;}
            }
	    	for(j = 0; j < k; ++j) {
                if(dp[i] == dp[idx[j]]*primes[j]) {idx[j]++;}
            }
		}
		return dp[n];
    }
};

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int i, j, k = primes.length;
    	int[] idx = new int[k];
        Arrays.fill(idx, 1);
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[1] = 1;
    	for (i = 2; i <= n; ++i) {	
	    	for (j = 0; j < k; ++j) {
                int tmp = dp[idx[j]]*primes[j];
                if (tmp < dp[i]) {dp[i] = tmp;}
            }
	    	for(j = 0; j < k; ++j) {
                if (dp[i] == dp[idx[j]]*primes[j]) {idx[j]++;}
            }
		}
		return dp[n];
    }
}

参考文献

【1】丑数_百度百科

【2】LeetCode 313. 超级丑数（动态规划）_Michael阿明的博客-CSDN博客