完全平方数

BraumAce2024年8月31日约 1205 字大约 4 分钟

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如， $1$ 、 $4$ 、 $9$ 和 $16$ 都是完全平方数，而 $3$ 和 $11$ 不是。

思路一：记忆化搜索

把 $1,4,9,16,...$ 这些完全平方数视作物品体积，物品价值都是 $1$ 。由于每个数（物品）选的次数没有限制，所以本题是一道标准的完全背包问题。

完全背包模板：完全背包

定义 dfs(i, j) 表示从前 $i$ 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 $j$ ，最少要选的数字个数。

考虑第 $i$ 个完全平方数 $i^2$ 选或不选：

不选：问题变成从前 $i−1$ 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 $j$ ，最少要选的数字个数，即 dfs(i, j) = dfs(i − 1, j)。
选：前提是 $j ≥ i^2$ 。问题变成从前 $i$ 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 $j − i^2$ ，最少要选的数字个数，即 dfs(i, j) = dfs(i, j − i^2) + 1。注意这里是 $i$ 而不是 $i−1$ ，因为我们可以继续选第 $i$ 个完全平方数。

这两种情况取最小值，就得到了 dfs(i, j)，即

dfs(i, j) = \left\{\begin{aligned} & dfs(i - 1, j), & j < i^2\\ & \min(dfs(i - 1, j), dfs(i, j - i^2) + 1), & j \geq i^2 \end{aligned}\right.

递归边界：dfs(0,0) = 0。因为没有数可以选了，且要得到的数等于 $0$ ，那么答案为 $0$ 。如果 $j > 0$ ，那么 dfs(0, j) = ∞，这里用 $\infty$ 表示不合法的状态，从而保证上式中的 min 取到合法的状态。注意本题是一定有解的，因为 $1$ 是完全平方数。

递归入口：由于 $i^2 ≤ n$ ，所以 $i ≤ \lfloor \sqrt{n} \rfloor$ ，所以递归入口为 $ dfs(\lfloor \sqrt{n} \rfloor, n)$，也就是答案。

代码：

class Solution {
    static int[][] memo = new int[101][10001];

    static {
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }
    }

    int dfs(int i, int j){
        if (i == 0){
            return j == 0 ? 0 : Integer.MAX_VALUE;
        }

        if (memo[i][j] != -1){
            return memo[i][j];
        }

        if (j < i * i){
            return memo[i][j] = dfs(i - 1, j);  // 超过范围，只能不选
        }

        return memo[i][j] = Math.min(dfs(i - 1, j), dfs(i, j - i * i) + 1);
    }

    public int numSquares(int n) {
        return dfs((int)Math.sqrt(n), n);
    }
}

思路二：递推

记忆化搜索是基于递归来实现的，首先找到最底下的叶子节点，再递归返回结果。在这个过程中，递归向上将结果返回的父节点是可以确定的，这样就可以省去刚开始向下「递」的过程。即自底向上递推计算，从 0 递推结果到 n，返回最后 n 处的结果即可。

具体来说，f[i][j] 的定义和 dfs(i,j) 的定义是一样的，都表示从前 $i$ 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 $j$ ，最少要选的数字个数。

相应的递推式（状态转移方程）也和 dfs 一样：

f[i][j] = \left\{\begin{aligned} & f[i - 1][j], & j < i^2\\ & \min(f[i - 1][j], f[i][j - i^2] + 1), & j \geq i^2 \end{aligned}\right.

初始值 f[0][0] = 0, f[0][j] = ∞，答案为 $f[⌊ \sqrt{n} ⌋][n]$ .

代码：

class Solution {
    public int numSquares(int n) {
        int[][] f = new int[101][n + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE);  // 初始化无穷大
        f[0][0] = 0;

        for (int i = 1; i * i <= n; i++){
            for (int j = 0; j <= n; j++){
                if (j < i * i){
                    f[i][j] = f[i - 1][j];  // 超过范围，只能不选
                } else {
                    // 比较选与不选方案的最小值
                    f[i][j] = Math.min(f[i - 1][j], f[i][j - i * i] + 1);
                }
            }
        }

        return f[(int)Math.sqrt(n)][n];
    }
}

空间优化

观察上面的状态转移方程，在计算 f[i] 时，只会用到 f[i − 1]，不会用到比 $i − 1$ 更早的状态。

因此可以去掉第一个维度，反复利用同一个长为 $n + 1$ 的一维数组。

递推式简化为，当 $j ≥ i^2$ 时，计算

f[j] = \min(f[j], f[j - i^2] + 1)

注意 $j < i^2$ 的递推式简化为 f[j] = f[j]，无需计算。

初始值 f[0] = 0, f[j] = ∞ (j > 0)。

答案为 f[n]。

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, Integer.MAX_VALUE);  // 初始化无穷大
        f[0] = 0;

        for (int i = 1; i * i <= n; i++){
            for (int j = i * i; j <= n; j++){
                // 比较选与不选方案的最小值
                f[j] = Math.min(f[j], f[j - i * i] + 1);
            }
        }

        return f[n];
    }
}

完全平方数

完全平方数

题意

思路一：记忆化搜索

思路二：递推

空间优化