给你一个整数
n，返回和为n的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，
1、4、9和16都是完全平方数，而3和11不是。示例 1：
输入：n =12输出：3解释：12 = 4 + 4 + 4
从动态规划划分来看是完全背包问题（物品可无限选），目标：装满容量，物品数量最少。
DP 定义
dp[i]：凑出数字 i 的最少平方数个数
初始化
- dp[0]=0
- 其余初始化为无穷大
状态转移
dp[i]=min(dp[i], dp[i−square]+1)
class Solution: def numSquares(self, n: int) -> int: squares = [] i = 1 while i * i <= n: squares.append(i * i) i += 1 INF = float('inf') dp = [INF] * (n + 1) dp[0] = 0 for s in squares: for i in range(s, n+1): dp[i] = min(dp[i], dp[i-s]+1) return dp[n]
