完全平方数:和为 n 的最少完全平方数个数
哪些公司问过
答案要点
- 建模为完全背包:平方数是可重复使用的物品,求凑成 n 的最少物品数
- dp[i] 表示和为 i 的最少平方数个数,dp[0]=0,dp[i]=min(dp[i-j*j]+1)
- 动态规划时间 O(n√n)、空间 O(n);BFS 按层搜索也能求最少个数
- 数学解法:四平方和定理保证答案不超过 4,用三平方和定理判断是否为 4
易错点
- 用贪心每次取最大平方数,得到的结果不是最少
- dp 初始化不当,比如把 dp[i] 初始化为 0 导致 min 失效
- 枚举 j 时边界写成 j*j<i,漏掉 i 本身是完全平方数的情况
面试官常见追问
- 为什么贪心每次取最大的平方数不对?
- BFS 解法怎么做,和 DP 比如何?
- 如果还要输出具体由哪些平方数组成怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场