题目链接 · 灵神原题解（署名来源）

一、记忆化搜索

把 $1,4,9,16,\cdots$ 这些完全平方数视作物品体积，物品价值都是 $1$。由于每个数（物品）选的次数没有限制，所以本题是一道标准的完全背包问题。原理见【基础算法精讲 18】。

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

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

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

这两种情况取最小值，就得到了 $\mathit{\text{dfs}}(i,j)$，即

$$\mathit{\text{dfs}}(i,j)=\{\begin{array}{ll}\mathit{\text{dfs}}(i-1,j),& j<i^2\\ min(\mathit{\text{dfs}}(i-1,j),\mathit{\text{dfs}}(i,j-i^2)+1),& j\ge i^2\end{array}$$

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

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

在计算 $n=7$ 的时候，如果选了 $4$，会递归到 $n=3$ 的情况。这个例子意味着多个测试数据之间可以共享记忆化搜索的结果。因此，把记忆化搜索的 $\mathit{\text{memo}}$ 数组声明为全局变量，这样可以在多个测试数据之间共享，从而减少计算量。Python 可以把 $\mathit{\text{dfs}}$ 写在类外面。

不用全局变量的写法见 322. 零钱兑换（我的题解），那道题和本题一样，也是完全背包求最小。

答疑

问：为什么本题的递归边界是 $i=0$？我之前做的那些 DP 题的递归边界都是 $i<0$。

答：本题最小的完全平方数是 $1^2$，递归到 $i=0$ 就说明所有完全平方数都考虑完了。其他题目最小的数一般是下标为 $0$ 的数，递归到 $i<0$ 就说明所有的数都考虑完了。

问：在 Java 等语言中，为什么可以返回 Integer.MAX_VALUE，这不会导致加法溢出吗？

答：通常来说要返回 Integer.MAX_VALUE / 2。如果从非法状态转移过来，这样写可以避免加法溢出。但本题比较特殊，由于 $1$ 是完全平方数，一个数一定可以分解为若干完全平方数的和。顺着 dfs(i, j - i * i) 往下递归，一定可以递归到 $j=0$ 的合法状态。如果实在无法理解，写 Integer.MAX_VALUE / 2 也没问题。

Python 解法1

# 写在外面，多个测试数据之间可以共享，减少计算量
@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int) -> int:
    if i == 0:
        return inf if j else 0
    if j < i * i:
        return dfs(i - 1, j)  # 只能不选
    return min(dfs(i - 1, j), dfs(i, j - i * i) + 1)  # 不选 vs 选

class Solution:
    def numSquares(self, n: int) -> int:
        return dfs(isqrt(n), n)

C++ 解法1

// C++ 版待补充

C++ 解法2

// 写在外面，多个测试数据之间可以共享，减少计算量
int memo[101][10001];

auto init = [] {
    memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
    return 0;
}();

int dfs(int i, int j) {
    if (i == 0) {
        return j == 0 ? 0 : INT_MAX;
    }
    int& res = memo[i][j]; // 注意这里是引用
    if (res != -1) { // 之前计算过
        return res;
    }
    if (j < i * i) {
        res = dfs(i - 1, j); // 只能不选
    } else {
        res = min(dfs(i - 1, j), dfs(i, j - i * i) + 1); // 不选 vs 选
    }
    return res;
}

class Solution {
public:
    int numSquares(int n) {
        return dfs(sqrt(n), n);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n\sqrt{n})$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(n\sqrt{n})$，单个状态的计算时间为 $\mathcal{O}(1)$，所以动态规划的时间复杂度为 $\mathcal{O}(n\sqrt{n})$。
• 空间复杂度：$\mathcal{O}(n\sqrt{n})$。保存多少状态，就需要多少空间。

二、1:1 翻译成递推

按照视频中的方法，我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

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

相应的递推式（状态转移方程）也和 $\mathit{\text{dfs}}$ 一样：

$$f[i][j]=\{\begin{array}{ll}f[i-1][j],& j<i^2\\ min(f[i-1][j],f[i][j-i^2]+1),& j\ge i^2\end{array}$$

初始值 $f[0][0]=0,f[0][j]=\mathrm{\infty }(j>0)$，翻译自递归边界 $\mathit{\text{dfs}}(0,0)=0$ 和 $\mathit{\text{dfs}}(0,j)=\mathrm{\infty }(j>0)$。

答案为 $f[\lfloor \sqrt{n}\rfloor ][n]$，翻译自递归入口 $\mathit{\text{dfs}}(\lfloor \sqrt{n}\rfloor ,n)$。

Python 解法3

N = 10000
f = [[0] * (N + 1) for _ in range(isqrt(N) + 1)]
f[0] = [0] + [inf] * N
for i in range(1, len(f)):
    for j in range(N + 1):
        if j < i * i:
            f[i][j] = f[i - 1][j]  # 只能不选
        else:
            f[i][j] = min(f[i - 1][j], f[i][j - i * i] + 1)  # 不选 vs 选

class Solution:
    def numSquares(self, n: int) -> int:
        return f[isqrt(n)][n]  # 也可以写 f[-1][n]

C++ 解法3

// C++ 版待补充

C++ 解法4

const int N = 10000;
int f[101][N + 1];

auto init = [] {
    ranges::fill(f[0], INT_MAX);
    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] = min(f[i - 1][j], f[i][j - i * i] + 1); // 不选 vs 选
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int numSquares(int n) {
        return f[(int) sqrt(n)][n]; // 也可以写 f[100][n]
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(N\sqrt{N})$。其中 $N={10}^4$。
• 空间复杂度：$\mathcal{O}(N\sqrt{N})$。

三、空间优化

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

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

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

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

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

初始值 $f[0]=0,f[j]=\mathrm{\infty }(j>0)$。

答案为 $f[n]$。

关于循环的顺序，见 视频讲解。

Python 解法5

N = 10000
f = [0] + [inf] * N
for i in range(1, isqrt(N) + 1):
    for j in range(i * i, N + 1):
        f[j] = min(f[j], f[j - i * i] + 1)  # 不选 vs 选

class Solution:
    def numSquares(self, n: int) -> int:
        return f[n]

C++ 解法5

// C++ 版待补充

C++ 解法6

const int N = 10000;
int f[N + 1];

auto init = [] {
    ranges::fill(f, INT_MAX);
    f[0] = 0;
    for (int i = 1; i * i <= N; i++) {
        for (int j = i * i; j <= N; j++) {
            f[j] = min(f[j], f[j - i * i] + 1); // 不选 vs 选
        }
    }
    return 0;
}();

class Solution {
public:
    int numSquares(int n) {
        return f[n];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(N\sqrt{N})$。其中 $N={10}^4$。
• 空间复杂度：$\mathcal{O}(N)$。

专题训练

见下面动态规划题单的「§3.2 完全背包」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府