企业官网建设流程全解析

心路历程：

动态规划问题，建模为：
状态：当前要处理的整数
动作：选哪一个满足要求的完全平方数
返回值：和为当前整数的最少完全平方数

注意的点：

1、边界条件中需要去除x<0的时候的情况，可以用正无穷配合返回值的min去除
2、注意候选动作应该从1开始，而不是0

解法：动态规划

背包问题建议递归动态规划

classSolution:defnumSquares(self,n:int)->int:@cachedefdp(x):# 和为x的完全平方数的最少个数ifx<0:returnfloat('inf')ifx==0:return0# 获取候选动作集合candicate=[]foriinrange(1,x+1):ifi*i<=x:candicate.append(i*i)else:breakres=[]foractionincandicate:res.append(1+dp(x-action))returnmin(res)returndp(n)

转化成数组动态规划

classSolution:defnumSquares(self,n:int)->int:# dp[i] 表示和为 i 所需的最少完全平方数的个数INF=float('inf')dp=[INF]*(n+1)dp[0]=0# 和为0需要0个完全平方数# 从小到大计算每个数字的最优解foriinrange(1,n+1):# 尝试所有可能的完全平方数j=1whilej*j<=i:dp[i]=min(dp[i],dp[i-j*j]+1)j+=1returndp[n]