这道题一种普遍的解法是动态规划。但是同样是动态规划,也有优劣之分。这篇博客贡献一份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.

 

丑数性质

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

动态规划

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

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

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注