Python DP solution, beats 93.7%, extremely detailed explanation
First, let\u2019s determine the route to solve this problem.\n\nWe need to find Nth number. So, what we need to do is:\n1. Find the 1st smallest number\n2. Find
First, let\u2019s determine the route to solve this problem.\n\nWe need to find **N**th number. So, what we need to do is:\n1. Find the 1st smallest number\n2. Find the 2nd smallest number\n3. Find the 3rd smallest number\n4. .....\n5. Finally, we find the **N**th number\n\nThis is actually Dynamic Programming.\n\nTake `primes = [2, 7, 13, 19]`, `n = 12` as an example:\n1. `n = 1`, of course, we return 1\n2. `n = 2`, we already have `[1]`, so, we do the calculation: `2 x 1, 7 x 1, 13 x 1, 19 x 1`, \nwe got `[2, 7, 13, 19]`, the smallest number is `2`, so, we return `2`.\n3. `n = 3`,  we already have `[1, 2]`. Last time, we chose `2` from `[2, 7, 13, 19]`, so, we do the calculation: `2 x 2` to replace the `2`. So, we got `[4, 7, 13, 19`, the smallest number is `4`, so, we return `4`.\n\n**Hold on ! Hold on !  Why we compute `2 x 2`  ????, not `2 x 3` or `7 x 2` or anything else ?**\n\nLet us figure out this problem !!!\n<br>\nWhat we need to do at each step is to find the next smallest number based on the numbers we have found.\nWe use Multiplication to produce the new number, so, what is the strategy for producing as small a number as possible?\n**We choose the smallest numbers to multiply !!!**\n<br>\nSo, at step 3, we already have `[1, 2]`, the primes are `[2, 7, 13, 19]`. Since we have compute `1 x primes`, this time, we just need to compute `2 x primes`.\nBut do we really need to do the calculation: `7 x 2`, `13 x 2`, `19 x 2` ???  \nNo! We have not chose `7 x 1, 13 x 1, 19 x 1` yet !!! There is no possibility that we will choose the smallest number from `[ 7 x 2, 13 x 2, 19 x 2]`.  So, we just need to compute `2 x 2` to get `[4, 7, 13, 19]`.\n\nThings get easy, right ???\n\nLet us keep on:\n\n4. n = 4\n```python\ndp = [1, 2, 4] # the numbers we have found\n\n# the index of the factors we choose from dp to multiply primes\n# e.g if we choose nth number as ugly number, then, index[n-1] += 1\n# so index will move to the right, which means we will replace the number\nindex = [2, 0, 0, 0]\n\n# ** number ** means we will choose this number\nugly_nums = [ 2 x dp[index[0]], **7 x dp[index[1]]**, 13 x dp[index[2]], 19 x dp[index[3]] ]\n```\n5. n = 5\n```python\ndp = [1, 2, 4, 7]\nindex  = [2, 1, 0, 0]\nugly_nums = [ **2 x 4**, 7 x 2, 13 x 1, 19 x 1 ]\n```\n6. n = 6\n```python\ndp = [1, 2, 4, 7, 8]\nindex  = [3, 1, 0, 0]\nugly_nums = [ 2 x 7, 7 x 2, **13 x 1**, 19 x 1 ]\n```\n7. n = 7\n```python\ndp = [1, 2, 4, 7, 8]\nindex  = [3, 1, 1, 0]\nugly_nums = [ **2 x 7**, **7 x 2**, 13 x 2, 19 x 1 ]\n```\nIf we have some same numbers, we choose only one value, but we will replace all of them at next step.\n8. n = 8\n```python\ndp = [1, 2, 4, 7, 8]\nindex  = [4, 2, 1, 0]\nugly_nums = [ **2 x 8**, 7 x 4, 13 x 2, 19 x 1 ]\n```\n......\nFinally, we will got the answers. \n**As you can see, we need to keep:**\n1.  The ugly number we found last time\n2.  All the ugly numbers we have found\n3.  The indexes in `dp` to multiply the prime number.\n\n**My code is as follows:**\n```python\nclass Solution(object):\n    def nthSuperUglyNumber(self, n, primes):\n        size = len(primes)\n        ugly, dp, index, ugly_nums = 1, [1], [0] * size, [1] * size\n        for i in range(1, n):\n            # compute possibly ugly numbers and update index\n            for j in range(0, size):\n                if ugly_nums[j] == ugly:\n                    ugly_nums[j] = dp[index[j]] * primes[j]\n                    index[j] += 1\n            # get the minimum\n            ugly = min(ugly_nums)\n            dp.append(ugly)\n        return dp[-1]\n```\n\n\n
[]