完全平方数：当数论遇上动态规划

还记得小学时学过的平方数吗？1, 4, 9, 16, 25...这些数有着独特的魅力。今天我们要聊的 LeetCode 279 题就和这些数字有关，它将带我们领略动态规划与数论的完美结合。

🎯 问题本质

给你一个正整数 n，要求找到最少需要多少个完全平方数相加得到 n。比如：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

输入：n = 13
输出：2
解释：13 = 4 + 9

乍看这道题，你可能会想："要不要把所有可能的组合都试一遍？"但等等，让我们用动态规划的思维来思考这个问题。

💡 思维转变：从暴力到动态规划

想象你正在玩一个数字游戏。要拼出数字n，你每次可以选择一个完全平方数。这不就像是用最少的硬币凑出一定金额吗？这种联想让我们找到了突破口。

🔍 动态规划的设计过程

让我们一步步构建解决方案：

1. 定义状态

dp[i] 表示组成数字 i 需要的最少完全平方数个数。这个定义直接对应我们要解决的问题。

2. 寻找状态转移方程

假设我们现在要求 dp[n]，我们可以：

• 先选一个完全平方数 j*j
• 然后问题就变成了求 dp[n - j*j]
• 遍历所有可能的 j，取最小值

所以状态转移方程就呼之欲出了： dp[i] = min(dp[i], dp[i - j*j] + 1)，其中 j*j ≤ i

class Solution {
    public int numSquares(int n) {
        // dp[i] 表示组成i需要的最少完全平方数个数
        int[] dp = new int[n + 1];
        
        // 初始化：假设最坏情况下都由1组成
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        // 计算所有小于等于n的完全平方数
        int maxSquareRoot = (int)Math.sqrt(n);
        int[] squares = new int[maxSquareRoot + 1];
        for (int i = 1; i <= maxSquareRoot; i++) {
            squares[i] = i * i;
        }
        
        // 动态规划过程
        for (int i = 1; i <= n; i++) {
            // 尝试每个小于i的完全平方数
            for (int j = 1; squares[j] <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - squares[j]] + 1);
            }
        }
        
        return dp[n];
    }
    
    // 数学方法：四平方和定理
    public int numSquaresMath(int n) {
        // 判断是否为完全平方数
        if (isSquare(n)) return 1;
        
        // 判断是否可以表示为两个完全平方数之和
        for (int i = 1; i * i <= n; i++) {
            if (isSquare(n - i * i)) return 2;
        }
        
        // 判断是否是4的倍数乘以8加7
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        
        // 其他情况下一定是3
        return 3;
    }
    
    private boolean isSquare(int n) {
        int sqrt = (int)Math.sqrt(n);
        return sqrt * sqrt == n;
    }
}

🎯 代码的精髓

我们的解法提供了两种思路：动态规划和数学方法。让我们深入理解动态规划解法的每个部分：

1. 预处理完全平方数：

   • 提前计算所有可能用到的完全平方数
   • 避免重复计算，提高效率

2. 状态转移的实现：

   • 对每个数i，尝试减去每个小于它的完全平方数
   • 取所有可能情况的最小值
   • 这个过程直观地体现了"选择"的概念

3. 初始化的考虑：

   • dp[0] = 0 作为基础case
   • 其他位置初始化为最大值，方便取最小值

💡 优化的艺术：数学方法

除了动态规划，这道题还有一个令人惊叹的数学解法 —— 四平方和定理：任何自然数都可以表示为最多四个完全平方数的和。

更进一步，我们可以证明：

1. 当n本身是完全平方数时，答案是1
2. 当n可以表示为两个完全平方数之和时，答案是2
3. 当n = 4^k * (8m + 7)时，答案是4
4. 其他情况下，答案是3

🤔 思考题

如果问题变成：要求所有加数都必须是不同的完全平方数，解法会有什么变化？提示：状态的定义可能需要加入"已使用的最大完全平方数"这个维度。

📝 面试技巧

在面试中遇到这道题，建议这样展示你的思路：

1. 先说明动态规划的思路：

   • 定义状态表示的含义
   • 推导状态转移方程
   • 解释为什么这个方程是正确的

2. 然后可以提到优化方向：

   • 预处理完全平方数
   • 提到数学方法的存在（加分项！）

记住，面试官更关心你的思维过程，而不仅仅是最终的解法。通过清晰地表达你如何一步步构建解决方案，你能展示出自己的问题解决能力。

---

作者：忍者算法
公众号：忍者算法

有人说算法是数学的艺术，这道题完美地诠释了这一点。它告诉我们，有时候一个问题可以有多种解法，而找到这些解法的过程，正是我们提升算法思维的过程。

#算法面试 #LeetCode #动态规划 #数学 #面试高频题