279. 完全平方数

---

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解题思路：使用动态规划算法求解。令dp[i]表示当前组成正整数i的完全平方数的最少个数，那么有dp[k**2+j] = min(dp[k**2+j],dp[j]+1)。即只要求解出dp[k**2]+dp[i-k**2] = 1 + dp[j]在k从1不断增大时的最小值即可。

Python3代码如下：

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [float('inf')]*(n+1)
        i = 1
        while i**2 <= n:
            dp[i**2] = 1
            i += 1
        for j in range(1,n):
            k = 1
            while k**2+j <= n:
                dp[k**2+j] = min(dp[k**2+j],dp[j]+1)
                k += 1
        return dp[-1]