1. 題目

編寫一段程序來查找第 n 個超級丑數。

超級丑數是指其所有質因數都是長度為 k 的質數列表 primes 中的正整數。

示例: 輸入: n = 12, primes = [2,7,13,19] 輸出: 32 解釋: 給定長度為 4 的質數列表 primes = [2,7,13,19]， 前 12 個超級丑數序列為：[1,2,4,7,8,13,14,16,19,26,28,32] 。說明: 1 是任何給定 primes 的超級丑數。給定 primes 中的數字以升序排列。 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。 第 n 個超級丑數確保在 32 位有符整數范圍內。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/super-ugly-number
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 類似題目：
  LeetCode 263. 丑數 && 264. 丑數 II（DP）（264題的升級版）
  LeetCode 1201. 丑數 III（最小公倍數+二分查找）
  程序員面試金典 - 面試題 17.09. 第 k 個數（set優先隊列/DP）

class Solution { public:int nthSuperUglyNumber(int n, vector<int>& primes) {int i, j, k = primes.size();vector<long> idx(k,1);vector<long long> dp(n+1, LONG_LONG_MAX);dp[1] = 1;for(i = 2; i <= n; ++i){ for(j = 0; j < k; ++j)if(dp[idx[j]]*primes[j] < dp[i])dp[i] = dp[idx[j]]*primes[j];for(j = 0; j < k; ++j)if(dp[i] == dp[idx[j]]*primes[j])idx[j]++;}return dp[n];} };

108 ms 9.4 MB

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 313. 超级丑数（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。