定义 dp[i] 表示“和为 i 的完全平方数的最少数量”；
初始状态：dp[0] = 0（和为0无需任何数），dp[i] 初始化为一个较大值（如 i，因为最坏情况是用 i 个1相加）；
状态转移：对于每个 i，遍历所有小于等于 i 的完全平方数 j²，则 dp[i] = min(dp[i], dp[i - j²] + 1)（即“不选j²的最少数量”和“选j²后i-j²的最少数量+1”取最小值）。

简单来说，要找和为i的最少完全平方数，就看所有能凑出i的组合（j² + (i-j²)），选其中数量最少的。

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取整数n
        int n = scanner.nextInt();

        Solution solution = new Solution();
        int result = solution.numSquares(n);

        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int numSquares(int n) {
        // dp[i] 表示和为i的完全平方数的最少数量
        int[] dp = new int[n + 1];

        // 初始化：最坏情况是用i个1相加，所以dp[i]初始为i
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            // 遍历所有小于等于i的完全平方数j²
            for (int j = 1; j * j <= i; j++) {
                // 状态转移：选j²的话，数量是dp[i-j²]+1，取最小值
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
}

🧠 通俗易懂解释

可以把问题理解为“用最少的平方数积木凑出数字n”：以 n=12 为例：

初始化 dp[12] = 12（最坏用12个1）；
遍历小于等于12的平方数：1、4、9；
- 选1：需要 dp[12-1]+1 = dp[11]+1，先记下来；
- 选4：需要 dp[12-4]+1 = dp[8]+1，比选1更少；
- 选9：需要 dp[12-9]+1 = dp[3]+1 = 3+1=4，比选4多；
最终 dp[12] 取最小值3（对应3个4）。

再看 n=13：

遍历平方数1、4、9、16（16>13跳过）；
选4：dp[13-4]+1 = dp[9]+1 = 1+1=2；
选9：dp[13-9]+1 = dp[4]+1 = 1+1=2；
最终最小值是2（4+9）。

⏱ 时间复杂度

O(n√n)

外层循环遍历 1~n，共 n 次；
内层循环遍历 1~√i，最多遍历 √n 次；
总操作数约为 n×√n，时间复杂度为 O(n√n)。

💾 空间复杂度

O(n)

需要一个长度为 n+1 的dp数组存储中间状态，空间复杂度为 O(n)。

额外优化（数学解法，可选）

根据“四平方和定理”，任何自然数都可以表示为最多4个完全平方数的和：

若n是完全平方数，答案为1；
若n满足 n = 4^k × (8m + 7)，答案为4；
否则检查是否能表示为2个完全平方数的和，能则答案为2，否则为3。

// 数学解法示例
class Solution {
    public int numSquares(int n) {
        // 检查是否是完全平方数
        if (isPerfectSquare(n)) return 1;
        // 检查是否满足4^k*(8m+7)
        if (check4k8m7(n)) return 4;
        // 检查是否能表示为两个完全平方数的和
        for (int i = 1; i * i < n; i++) {
            if (isPerfectSquare(n - i * i)) return 2;
        }
        return 3;
    }
    
    // 判断是否是完全平方数
    private boolean isPerfectSquare(int n) {
        int sqrt = (int) Math.sqrt(n);
        return sqrt * sqrt == n;
    }
    
    // 检查是否满足n = 4^k*(8m+7)
    private boolean check4k8m7(int n) {
        while (n % 4 == 0) {
            n /= 4;
        }
        return n % 8 == 7;
    }
}

数学解法时间复杂度可优化至 O(√n)，空间复杂度 O(1)，适合追求极致效率的场景。

记录每个数的完全平方数