279. 完全平方数#

class Solution {
    public int numSquares(int n) {
        // dp[i] 表示“组成整数 i 所需的最少完全平方数个数”
        int[] dp = new int[n + 1];

        // 初始化为最大值，表示当前还未找到可行方案（后续通过取最小值更新）
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 基础状态：组成 0 不需要任何数字
        dp[0] = 0;

        // 预处理：先计算所有 <= n 的完全平方数，避免在双循环中重复乘法
        int maxSquareRoot = (int)Math.sqrt(n); // n 的最大平方根
        int[] squares = new int[maxSquareRoot + 1]; // squares[i] = i*i（下标从 1 开始使用）
        for (int i = 1; i <= maxSquareRoot; i++) {
            // 记录第 i 个完全平方数
            squares[i] = i * i;
        }

        // 动态规划主过程：从小到大计算每个 i 的最优解
        for (int i = 1; i <= n; i++) {
            // 枚举所有 <= i 的完全平方数作为“最后一步”
            for (int j = 1; squares[j] <= i; j++) {
                // 状态转移：dp[i] = min(dp[i], dp[i - square] + 1)
                // 含义：先凑出 i - squares[j]，再加上这个平方数 squares[j]
                dp[i] = Math.min(dp[i], dp[i - squares[j]] + 1);
            }
        }

        // 返回组成 n 的最少完全平方数个数
        return dp[n];
    }

    // 数学方法：四平方和定理
    public int numSquaresMath(int n) {
        // 情况 1：n 本身是完全平方数，答案直接为 1
        if (isSquare(n)) return 1;

        // 情况 2：判断是否能表示成两个完全平方数之和
        for (int i = 1; i * i <= n; i++) {
            // 若 n - i*i 也是完全平方数，则答案为 2
            if (isSquare(n - i * i)) return 2;
        }

        // 根据四平方和定理的推论，先剥离 4 的因子，不影响最终分类
        while (n % 4 == 0) n /= 4;
        // 若化简后满足 n % 8 == 7，则答案必为 4
        if (n % 8 == 7) return 4;

        // 其余情况既不是 1、2、4，则答案一定为 3
        return 3;
    }

    private boolean isSquare(int n) {
        // 先取整数平方根
        int sqrt = (int)Math.sqrt(n);
        // 通过平方回验，判断是否是完全平方数
        return sqrt * sqrt == n;
    }
}