企业官网建设流程全解析

思路：

dp[i]定义为凑成i所需要的最少完全平方数为dp[i]。求的是最少数量。

状态转移方程：dp[i]=min(dp[i-j**2]+1,dp[i])

def perfectSquares(n): #q求凑成i的最少完全平方数的数量 dp=[float('inf')]*(n+1) dp[0]=0 for i in range(1,n+1): j=1 while j*j<=i: dp[i]=min(dp[i-j**2]+1,dp[i]) j+=1 return dp[n] def main(): n=int(input()) res=perfectSquares(n) print(res) if __name__=="__main__": main()