perfect_squares.py 文件源码

def numSquares1(n):
    dp = [-1 for i in range(n + 1)]
    dp[1] = 1
    for i in range(2, n + 1):
        j = 1
        m = sys.maxint
        while j * j <= i:
            if j * j == i:
                m = 1
                break
            m = min(m, dp[i - j * j] + 1)
            j += 1
        dp[i] = m
    return dp[n]

# print(numSquares1(10234))