完全平方数

怎样从“n=12 最少几个完全平方和=3(4+4+4)。”推导出 背包 DP · 完全平方，并证明每次状态变化都不会漏掉答案？

中心结论：dp[i]=min(dp[i-j*j]+1) for j*j<=i;dp[0]=0。

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

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

在本站主例中，n=12 最少几个完全平方和=3(4+4+4)。

算法最终需要得到或观察：答案 3。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 dp 数组、j*j。
3. 3转移每一步按照 dp[i]=min(dp[i-j*j]+1) for j*j<=i;dp[0]=0。
4. 4收尾读取 答案 3。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：dp 数组、j*j。

由拉格朗日的四平方定理可得，每个自然数都可以表示为四个整数平方之和。 其中四个数字是整数。四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。 四平方和定理可以推出三平方和推论：当且仅当 {{ }} n \neq 4^{k} \times (8m + 7){{ }} 时，n 可以被表示为至多三个正整数的平方和。所以当 {{ }} n = 4^{k} (8m + 7){{ }} 时，n 只能被表示为四个正整数的平方和。此时我们可以直接返回 4。 当 {{ }} n \neq 4^{k} \times (8m + 7){{ }} 时，需要判断 n 到底可以分解成几个完全平方数之和。答案肯定是 1，2，3 中的一个。题目要求我们求最小的，所以从 1 开始一个个判断是否满足。如果答案为 1，代表 n 为完全平方数，这很好判断。如果答案为 2，代表 {{ }} n = a^{2} + b^{2} {{ }}，枚举 {{ }} 1 \leqslant a \leqslant \sqrt{n} {{ }}，判断 {{ }} n - a^{2} {{ }} 是否为完全平方数。当 1 和 2 都排除了，剩下的答案只能为 3 了。

dp[i]=min(dp[i-j*j]+1) for j*j<=i;dp[0]=0。

执行过程中持续维护：dp 数组、j*j。

正确性依赖以下不变量：dp[i] 最少平方数个数。

面试时可以压缩为：完全背包式 DP O(n·sqrt n)。

落到当前题，执行机制可以压缩为：dp[i]=min(dp[i-j*j]+1) for j*j<=i;dp[0]=0。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入n=12 最少几个完全平方和=3(4+4+4)。 因为：dp[i]=min(dp[i-j*j]+1) for j*j<=i;dp[0]=0。
2. 2dp[1] 用硬币 1: 0+1 = 1尝试每种硬币松弛。 因为：完全背包正序枚举容量。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4dp[4] 用硬币 1: 3+1 = 4尝试每种硬币松弛。 因为：完全背包正序枚举容量。
5. 5dp[5] 用硬币 1: 1+1 = 2尝试每种硬币松弛。 因为：完全背包正序枚举容量。
6. 6dp[7] 用硬币 1: 3+1 = 4尝试每种硬币松弛。 因为：完全背包正序枚举容量。
7. 7无法凑出返回 dp[amount]。 因为：O(amount·|coins|)。
8. 8收尾与复杂度答案 3。 因为：时间 O(n) · 空间 O(1)。dp[i]=min(dp[i-j*j]+1) for j*j<=i;dp[0]=0。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "math"

func numSquares(n int) int {
	if isPerfectSquare(n) {
		return 1
	}
	if checkAnswer4(n) {
		return 4
	}
	for i := 1; i*i <= n; i++ {
		j := n - i*i
		if isPerfectSquare(j) {
			return 2
		}
	}
	return 3
}

// 判断是否为完全平方数
func isPerfectSquare(n int) bool {
	sq := int(math.Floor(math.Sqrt(float64(n))))
	return sq*sq == n
}

// 判断是否能表示为 4^k*(8m+7)
func checkAnswer4(x int) bool {
	for x%4 == 0 {
		x /= 4
	}
	return x%8 == 7
}

func main() {
    // 1. 主例
    //    输入：mode="coin-change", coins=[1,4,9], amount=12
    //    期望：答案 3。
    //
    // 2. 失败 / 未命中
    //    检查：sqrt 循环 j 即可。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC322 零钱；LC139 单词拆分
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意n=12 最少几个完全平方和=3(4+4+4)。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化dp[i]=min(dp[i-j*j]+1) for j*j<=i;dp[0]=0。
4. 4证明dp[i] 最少平方数个数。
5. 5复杂度时间 O(n)，空间 O(1)