给出一个数，用最少的可开方的数相加得出这个数，例如12=4+4+4，输出3 13 = 4+9，输出2
如果要使用动态规划来求解，我们可以先用递归的方法实现一遍，这样思路会比较清晰。
首先是找到所有的比该数n小的平方数，n减去这些平方数得到一个新的数m，那么问题就变成了找m的最少开方数。同时注意到问题是找最少，那么肯定要前后情况进行对比，因此需要设置一个初始状态，设值为n，因为最糟糕的情况就是n个1相加。
递归退出的条件是当前的n为0，此时返回0
代码如下，当n比较大的时候需要比较长的时间
class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ nums = [i**2 for i in range(1, int(n**0.5+1))] res = n return self.helper(n, nums,res) def helper(self, n, nums,res): if n == 0: return 0 else: for i in nums: if n >= i: res = min(res, self.helper(n-i,nums,res) + 1) return res s = Solution() s.numSquares(40) # output: 2有了上面的思路，那么我们可以将其改为动态规划的方法，用bottom-up方法比较好。设dp[i]是i数对应的最少平方数，那么首先初始化dp[i]为n，向上面一样，根据上面的递归式子，dp[i] = min(dp[i], dp[i-j]+1)，j是平方数，那么就可以写出下面的代码，运行效率要比上面的高很多。
class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ nums = [i**2 for i in range(1, int(n**0.5+1))] dp = [n]*(n+1) dp[0] = 0 for i in range(1,n+1): for j in nums: dp[i] = min(dp[i],dp[i-j]+1) return dp[-1] s = Solution() s.numSquares(40) # output: 2