完全平方数

题目要求 给定一个正整数 n，返回若干个正的完全平方数相加得到 n 时，所需的最少数量。完全平方数是整数的平方，例如 1 = 1²、4 = 2²、9 = 3²、16 = 4²。 和必须刚好等于 n。 同一个完全平方数可以使用任意次。 只返回数量，不需要返回具体分解；加数的先后顺序不影响答案。 约束：1 <= n <= 10^4。 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4，需要 3 个完全平方数。 输入：n = 13 输出：2 解释：13 = 9 + 4，需要 2 个完全平方数。 下面使用 Python 3.9+ 逐步构建解法，适合已经理解函数、循环和基础递归，希望进一步理解动态规划的读者。 Step 1：先确定剩余和为 0 的答案 先拿最大的平方数，会不会让数量最少？对 n = 12，这一选择得到： 12 -> 先拿 9 -> 剩下 3 -> 再拿 1 + 1 + 1 总共：9 + 1 + 1 + 1，4 个 但是 4 + 4 + 4 只需要 3 个。当前的想法是“每次选不超过剩余和的最大平方数”，它在 12 上已经失败：单次拿得更多，不保证最后用得更少。 ...