279. 完全平方数(中等）-动态规划

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是

分析

• 定义最小问题，其实大部分和原问题一样
• 定义转移方程，不需要按照顺序依次，因为只要是前面计算过的都可以用，可以跳着使用
• 反着来，假设有这么个方案，那么那必然是等于前面那个方案+1（这个就是一个平方数），最后一个平方数可以遍历的

class Solution:
    def numSquares(self, n: int) -> int:
        # 这个最小问题也是和为 n 的完全平方数的最少数量 
        # 只不过它和之前1->sqrt(n)所有的位置最小数量+1进行比较得到它的最小值
        # 由小到大
      

        dp = [0] + [n]*n

        for i in range(1, n + 1):
            for j in range(1, int(math.sqrt(i)) + 1):
                dp[i] = min(dp[i], dp[i - j*j] + 1)
        
        return dp[-1]