/*

    和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];

    }