力扣 279. 完全平方数

动态规划

def numSquares(n):
    # 动态规划
    dp = [0 for _ in range(n + 1)]
    for i in range(1, n + 1):
        dp[i] = i
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[-1]