class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""dp = [float('inf')]*(n+1)num = int(n**(0.5))+1 # 0.5不能写成1/2,因为在python2中1/2等于0dp[0] = 0for i in range(1,num):for j in range(i*i,n+1):dp[j] = min(dp[j],dp[j-i*i]+1)return dp[n]
题目链接：279. 完全平方数 - 力扣（LeetCode）
如果使用的是Python3
则可以写成1/2
如下
class Solution:def numSquares(self, n: int) -> int:num = int(n**(1/2))+1dp = [float('inf')] * (n+1)dp[0] = 0for i in range(1,num):for j in range(i*i,n+1):dp[j] = min(dp[j],dp[j-i*i]+1)return dp[n] 
