给定一个正整数 n，求组成 n 的完全平方数的最少数量（例如 n=12 时返回 3，因为 12=4+4+4）。请实现该算法并说明思路。
考察说明
考察动态规划建模、子问题划分与算法复杂度分析
回答思路
- 正确建立 dp 状态：dp[i] 表示 i 的最少平方数个数
- 正确写出状态转移方程：dp[i]=min(dp[i], dp[i-j*j]+1)
- 能处理边界条件（如 i 本身为平方数）并给出复杂度分析
- 能说明贪心失效原因并解释动态规划的必要性
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。