思路
初始值 dp[0]=0
假设要求当前和为n的最小数量，可以依次去查找 n-(小于等于n的完全平方数）的值所需最小完全平方个数+1
class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""dp=[0]*(n+1)dp[0]=0for i in range(1,n+1):#看题目提示，t不会超过nt = pow(10,4)j =1while pow(j,2)<=i:t = min(t,dp[i-pow(j,2)])j+=1dp[i]=t+1return dp[n]