LeetCode_313: Super Ugly Number

这道题一种普遍的解法是动态规划。但是同样是动态规划，也有优劣之分。这篇博客贡献一份36ms（80%+）的答案，推荐这份答案不仅是因为速度，还是因为这种思路十分清晰，当然也可以参考讨论区中的7行的动态规划答案，也是十分优秀的。

题目

Write a program to find the n^th super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [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] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000.
(4) The n^th super ugly number is guaranteed to fit in a 32-bit signed integer.

 

丑数性质

动态规划

这道题在动态规划中，通过不断更新可能的最小值，分析此时最小值的性质，下面代码中可能的最小值都是当前最小值再乘以一个基，来进最小值的更新。刚刚使用掉哪个基的值，就使用对应的基进行替换更新。

1. 初始化可能的最小值
2. 进行循环迭代，顺序产生丑数，产生的丑数由小到大排列
3. 每次从可能的最小值中取出最小值（放入丑数数组）
4. 更新：将所有可能最小值中等于刚刚产生值的最小值（可能多个）进行替换，替换的方式就是乘以对应的基（每个可能的最小值对应一个多个基，多了重复不要紧，前面就是去重复的操作）

代码

class Solution {
public:
	int nthSuperUglyNumberDP2(int n, vector<int>& primes) {
		vector<int> idx(primes.size(), 0);				// current index for primes[i] in dp
		vector<int> next(primes.size(), 0);				// next available primes[i] * dp[idx[i]]
		vector<int> dp(n, 0); dp[0] = 1;				// dp for answer

		for (int i = 0; i < primes.size(); i++) {
			next[i] = primes[i];                                    // initialize the values
		}

		for (int i = 1; i < n; i++) {
			dp[i] = INT_MAX;
			for (int j = 0; j < primes.size(); j++) {
				dp[i] = (std::min)(dp[i], next[j]);                 // find min in next for dp[i] 
			}
			for (int j = 0; j < primes.size(); j++) {
				if (dp[i] == next[j]) {
					next[j] = primes[j] * dp[++idx[j]];             // update idx and next
				}
			}
		}
		return dp[n - 1];
	}
};