LeetCode_313: Super Ugly Number

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

题目

Write a program to find the nth 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 ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

 

丑数性质

博主最开始没做出这道题,因为理解错了题目中说的丑数。[mathjax]题目中说的丑数可以用如下公式表示,以$latex P$为基的丑数,可以表示为丑数基的相乘,其中$latex n_i$可以等于0,所以1是所有基的丑数。
$$U=\Pi_i P_i^{n_i}$$

动态规划

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

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

 

发表评论