# Dynamic Programming Solution w/ Explaination

• Idea is to use an array to keep track of a pointer for each prime number.

``````dp[i] = min(prime1 * dp[p1], prime2 * dp[p2] ...)
``````

`prime 1 * dp[p1]` gives the multiple of prime 1 that is JUST greater than dp[i-1]. We iterate over all primes and test which is the smallest. Then we do a second iteration to increment the all pointers which have primes that match the smallest number. End the loop when our res gets to size of n.

``````def nthSuperUglyNumber(self, n, primes):
k = len(primes)
# keep a set of pointers for each prime number
primes_p = [0 for i in range(k)]
res = [1]
while len(res) != n:
# at each iteration, search for the smallest available prime * res[pointer]
smallest = sys.maxint
for i in range(k):
smallest = min(smallest, primes[i] * res[primes_p[i]])
res.append(smallest)
for i in range(k):
if primes[i] * res[primes_p[i]] == smallest:
primes_p[i] += 1
return res[-1]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.