[LeetCode]313. Super Ugly Number

题目描述

思路

动态规划
保持结果序列递增，需要确保每次放入结果序列的数是当前乘积最小，当前的乘积是由产生序列的数和素数数组里的数乘积得到的，因此需要一个状态数组来保存对于素数数组里的每个数，乘到了数组里的第几个数，最终生成序列

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int primesNum = primes.size();
        vector<int> uglyArr(n, INT_MAX), indexArr(primesNum, 0);
        uglyArr[0] = 1;
        for (int i = 1; i < n; ++i) {
            // 更新序列中的数
            for (int index = 0; index < primesNum; index++) uglyArr[i] = min(uglyArr[i], uglyArr[indexArr[index]] * primes[index]);
            // 序列中的数更新后，更新index数组
            for (int index = 0; index < primesNum; index++) indexArr[index] += (uglyArr[i] == uglyArr[indexArr[index]] * primes[index]);
        }
        return uglyArr[n - 1];
    }
};

int main() {
    vector<int> primes = { 2,7,13,19 };
    Solution s;
    cout << s.nthSuperUglyNumber(11, primes) << endl;

    system("pause");
    return 0;
}