279. 完全平方数V2

INVALID

用一个INVALID的数值来表示不可达值.

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        coins = []
        
        for i in range(1,n+1):
            if i*i<=n:
                coins.append(i*i)

        INVALID=n+1
        dp = [INVALID]*(n+1)
        dp[0] = 0
        
        for i in range(1, n+1):
            for c in coins:
                if i>=c:
                    dp[i] = min(dp[i],dp[i-c]+1)
        return dp[-1]