Dynamic Programming in Java Based on Ugly Number II


  • 0
    N
    //Dynamic Programming
    public int nthSuperUglyNumber(int n, int[] primes) {
        // primes.length is # of subsequences
        int[] ugly = new int[n];
        ugly[0] = 1;
        int k = primes.length;
        // index number of each subsequence
        // use the index to get the value of last number in the subsequence
        int[] index = new int[k];
        int[] nextNum = Arrays.copyOf(primes,k);
        for(int i=1;i<n;i++){
           int minVal = getMin(nextNum);
           ugly[i] = minVal;
           for(int j=0;j<k;j++){
               if(minVal == nextNum[j]){
                   nextNum[j] = ugly[++index[j]]*primes[j];
               }
           }
        }
        return ugly[n-1];
    }
    
    public int getMin(int[] nums){
        int min = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
             min = Math.min(min,nums[i]);
        }
        return min;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.