【LeetCode 热题 100】279. 完全平方数——（解法一）记忆化搜索
Problem: 279. 完全平方数
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(n * sqrt(n))
- 空间复杂度：O(n * sqrt(n))
整体思路
这段代码旨在解决一个经典的数论与动态规划问题：完全平方数 (Perfect Squares)。问题要求找到和为 n 的最少完全平方数（例如 1, 4, 9, 16, ...）的数量。
该算法采用的是 自顶向下（Top-Down）的动态规划，即 记忆化搜索 (Memoization)。它巧妙地将原问题转化为一个经典的组合优化模型：完全背包问题 (Unbounded Knapsack Problem)。
-
问题转化：完全背包模型
- 背包容量 (Capacity)：目标整数
n。 - 物品 (Items)：所有小于等于
n的完全平方数，即1^2, 2^2, 3^2, ..., i^2其中i*i <= n。 - 物品价值/重量：在这个问题中，我们不关心物品的“价值”，而是关心物品的“数量”。可以认为每个物品的“价值”是1。
- 目标：用最少的物品（完全平方数）恰好装满背包（使它们的和等于
n）。 - “完全/无界”的含义：每种物品（每个完全平方数）都可以无限次地使用。例如，
12 = 4 + 4 + 4。
- 背包容量 (Capacity)：目标整数
-
状态定义与递归关系
- 算法的核心是递归函数
dfs(i, j)，其状态定义为：
dfs(i, j)= 使用物品1^2, 2^2, ..., i^2来凑成和为j时，所需要的最少物品数量。 - 对于当前状态
dfs(i, j)，我们面临一个选择，即是否使用物品i^2：
a. 不使用i^2：如果我们决定不使用i^2，那么问题就变成了“使用物品1^2, ..., (i-1)^2来凑成和为j”，这对应于递归调用dfs(i-1, j)。
b. 使用i^2：如果我们决定使用i^2（前提是j >= i*i），那么我们已经用掉了一个物品，剩下的问题是“使用物品1^2, ..., i^2来凑成和为j - i*i”。注意这里仍然是dfs(i, ...)而不是dfs(i-1, ...)，因为这是完全背包问题，i^2可以重复使用。这对应于dfs(i, j - i*i) + 1。 dfs(i, j)的最终结果就是这两种选择中的最小值。
- 算法的核心是递归函数
-
记忆化与基础情况
- 记忆化：为了避免重复计算，算法使用了一个二维数组
memo。memo[i][j]存储dfs(i, j)的结果。在函数开头检查memo可以将时间复杂度从指数级降至多项式级。 - 基础情况：
if (i == 0)是递归的出口。当没有物品可用时（i=0），如果目标和j恰好也是0，说明成功了，用了0个物品；否则，无法凑成，返回一个极大值Integer.MAX_VALUE表示此路不通。
- 记忆化：为了避免重复计算，算法使用了一个二维数组
完整代码
import java.util.Arrays;class Solution {// memo: 记忆化数组。memo[i][j] 存储用 1^2...i^2 凑成 j 所需的最少平方数。// 声明为 static，使得 memo 表在所有 Solution 对象实例之间共享，并能在 static 块中初始化。// 题目约束 n <= 10000，所以 sqrt(n) <= 100。private static final int[][] memo = new int[101][10001];// static 初始化块：在类加载时执行一次，用于初始化 memo 数组。static {for (int[] row : memo) {// 将所有值填充为 -1，表示该状态尚未计算。Arrays.fill(row, -1);}}/*** 计算和为 n 的最少完全平方数的数量。* @param n 目标整数* @return 最少完全平方数的数量*/public int numSquares(int n) {// 启动递归。// 第一个参数是可用的最大平方数的底数，即 sqrt(n)。// 第二个参数是目标和 n。return dfs((int) Math.sqrt(n), n);}/*** 记忆化搜索函数。* @param i 表示当前可以使用的最大平方数是 i*i。* @param j 表示当前需要凑成的目标和。* @return 凑成 j 所需的最少平方数数量。*/private int dfs(int i, int j) {// 基础情况（递归出口）：当没有平方数可用时 (i=0)if (i == 0) {// 如果目标和 j 也是 0，说明成功凑出，用了0个数。// 否则，无法凑出，返回一个极大值表示此路不通。return j == 0 ? 0 : Integer.MAX_VALUE;}// 记忆化检查：如果 memo[i][j] 不为 -1，说明这个子问题已计算过，直接返回结果。if (memo[i][j] != -1) {return memo[i][j];}// 剪枝优化：如果当前目标和 j 小于当前考虑的平方数 i*i，// 那么 i*i 肯定不能用。问题直接退化为用 1^2...(i-1)^2 去凑 j。if (j < i * i) {return memo[i][j] = dfs(i - 1, j);}// 状态转移：// 我们在两种选择中取最小值：// 1. dfs(i - 1, j): 不使用 i*i 这个数。// 2. dfs(i, j - i * i) + 1: 使用至少一个 i*i。return memo[i][j] = Math.min(dfs(i - 1, j), dfs(i, j - i * i) + 1);}
}
时空复杂度
时间复杂度：O(n * sqrt(n))
- 状态数量：由于记忆化的存在，每个状态
(i, j)只会被实际计算一次。i的范围是从0到(int)Math.sqrt(n)。j的范围是从0到n。- 因此，总的状态数量是
(sqrt(n) + 1) * (n + 1)。
- 每个状态的计算时间：在
dfs函数内部，除了递归调用，其他的操作（比较、加减、Math.min）都是 O(1) 的。
综合分析：
总的时间复杂度等于（状态数量）×（每个状态的计算时间），即 O(sqrt(n) * n)。
空间复杂度：O(n * sqrt(n))
- 记忆化数组：算法创建了一个
memo二维数组来存储所有子问题的解。其大小为101 * 10001，对应于(sqrt(n_max) + 1) * (n_max + 1)。因此，这部分空间占用为 O(n * sqrt(n))。 - 递归调用栈：递归的深度也需要考虑。在最坏的情况下，例如
dfs(1, n)，递归链可能是dfs(1, n) -> dfs(1, n-1) -> ...，深度可达 O(n)。另一个方向是dfs(sqrt(n), n) -> dfs(sqrt(n)-1, n) -> ...，深度是 O(sqrt(n))。最大深度是 O(n)。 - 综合分析：
- 记忆化数组的空间开销是 O(n * sqrt(n))。
- 递归栈的空间开销是 O(n)。
- 由于
n * sqrt(n)是主导项，因此最终的空间复杂度为 O(n * sqrt(n))。
参考灵神