边工作边刷题：70天一遍leetcode: day 24-2

Super Ugly Number

这题和名字一样恶心。逻辑不好想，也可能我是天生对数的结构不太敏感。但是算法结构很简单，所以建议最好背答案
结构：

• 维护一个数组：记录每个prime的当前指针，下一个数就是最小的prime指向的数和其乘积。
• 有可能多个prime都对应min，比如3X5和5X3，所以在判断min后再loop一遍primes来移动指针

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        dp = [1]*n
        pp = [0]*len(primes) # pointer to current pos in dp
        for i in range(1, n):
            min = sys.maxint
            for k in range(len(primes)):
                if min>dp[pp[k]]*primes[k]:
                    min = dp[pp[k]]*primes[k]
                
            dp[i]=min
            for k in range(len(primes)):
                if min==dp[pp[k]]*primes[k]:
                    pp[k]+=1
        
        return dp[n-1]