image.png

1. 正整数n可以看做n = a*a+B，继而B=b*b+C，以此类推；
2. n的平方数个数的最优解dp[n] = 1 + dp[n']，且n'小于n，n'的变化范围[1, n-1];
3. 对于每一个n，找到1到n-1中，谁的解最小，那么n的解就是它+1；
4. 1到n-1之间的数为i-j*j。

Python3代码

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [int(1e9) for i in range(n+1)]
        dp[0] = 0
        for i in range(1, n+1):
            j = 1
            while j*j <= i:
                dp[i] = min(dp[i], dp[i-j*j]+1)
                j+=1
        return dp[n]