题目

super-ugly-number

2. 算法

* 直接模拟

* 直接模拟优化

3. 代码

* 直接模拟

class Solution {

public:

    int nthSuperUglyNumber(int n, vector<int>& primes) {

        vector<int> res(1, 1), idx(primes.size(), 0);

        while (res.size() < n) {

            vector<int> tmp;

            int mn = INT_MAX;

            for (int i = 0; i < primes.size(); ++i) {

                tmp.push_back(res[idx[i]] * primes[i]);

            }

            for (int i = 0; i < primes.size(); ++i) {

                mn = min(mn, tmp[i]);

            }

            for (int i = 0; i < primes.size(); ++i) {

                if (mn == tmp[i]) ++idx[i];

            }

            res.push_back(mn);

        }

        return res.back();

    }

};

* 直接模拟优化

class Solution {

public:

    int nthSuperUglyNumber(int n, vector<int>& primes) {

        vector<int> dp(n, 1), idx(primes.size(), 0);

        for (int i = 1; i < n; ++i) {

            dp[i] = INT_MAX;

            for (int j = 0; j < primes.size(); ++j) {

                dp[i] = min(dp[i], dp[idx[j]] * primes[j]);

            }

            for (int j = 0; j < primes.size(); ++j) {

                if (dp[i] == dp[idx[j]] * primes[j]) {

                    ++idx[j];

                }

            }

        }

        return dp.back();

    }

};