心路历程动态规划问题建模为状态当前要处理的整数动作选哪一个满足要求的完全平方数返回值和为当前整数的最少完全平方数注意的点1、边界条件中需要去除x0的时候的情况可以用正无穷配合返回值的min去除2、注意候选动作应该从1开始而不是0解法动态规划背包问题建议递归动态规划classSolution:defnumSquares(self,n:int)-int:cachedefdp(x):# 和为x的完全平方数的最少个数ifx0:returnfloat(inf)ifx0:return0# 获取候选动作集合candicate[]foriinrange(1,x1):ifi*ix:candicate.append(i*i)else:breakres[]foractionincandicate:res.append(1dp(x-action))returnmin(res)returndp(n)转化成数组动态规划classSolution:defnumSquares(self,n:int)-int:# dp[i] 表示和为 i 所需的最少完全平方数的个数INFfloat(inf)dp[INF]*(n1)dp[0]0# 和为0需要0个完全平方数# 从小到大计算每个数字的最优解foriinrange(1,n1):# 尝试所有可能的完全平方数j1whilej*ji:dp[i]min(dp[i],dp[i-j*j]1)j1returndp[n]