企业官网建设流程全解析

某手机大厂的2019秋招算法题单里，有一道讨论度很高的题：最少立方数之和。题目很短：给定一个正整数 n，问 n 至少能拆成几个正整数的立方数之和。第一次拿到这道题，很多人第一反应是 DFS，因为“拆数”天然适合递归；但真正要在笔试或现场手写里做到干净又稳定，DP 才是多数面试官期待的标准答案。这题考的点很扎实：状态怎么定义、转移怎么写、边界怎么处理、DFS 如何通过记忆化收敛成 DP，从暴力到最优的完整链路都有。下面按我平时刷题的习惯，把这道题的 DFS、BFS、DP 三种思路放在同一张图上讲清楚，再补上面试追问时容易暴露的几个坑。

1. 这道题的面试味道：一句话题干，三层隐藏考点

1.1 题干和几个手算样例

先明确题目细节。给定正整数 n，要求用若干个正整数的立方数相加得到 n，问最少需要多少个。立方数指的是 1^3、2^3、3^3……这个集合里的数，同一个立方数可以重复使用。几个简单样例：

• n = 1，答案是 1，因为 1 = 1^3。
• n = 8，答案是 1，因为 8 = 2^3。
• n = 9，答案是 2，因为 9 = 2^3 + 1^3。
• n = 15，答案是 8，因为 15 = 2^3 + 1^3 × 7，也就是 8 + 1 × 7。
• n = 48，答案是 6，因为 48 = 2^3 × 6，也就是八个 8 之外的更优拆法。

能看到候选立方数其实增长很快。1^3 = 1，2^3 = 8，3^3 = 27，4^3 = 64……如果 n 不超过 10^6，只需要用到 100^3，因为 100^3 = 1,000,000。所以候选集合大小 m 大约是 n 的立方根，这是后面所有复杂度分析的出发点。很多人在面试里栽跟头，不是不会写状态转移，而是没说清楚 m 这个量级。

1.2 为什么“先取最大立方数”的贪心会翻车

不少人的第一反应是贪心：每次取不超过剩余值 n 的最大立方数。但是贪心在这里是错的，面试官很喜欢拿这个当追问。看 n = 48：候选立方数只有 1、8、27。贪心先取 27，剩余 21；取 8，剩余 13；再取 8，剩余 5；剩下 5 个 1。总个数是 1 + 2 + 5 = 8。但正确答案是 6，因为 48 = 8 × 6，六个 8 直接解决。

问题出在“局部最大”破坏了整体最优。贪心假设每次吃掉越大的立方数，后续就越省，但实际候选数并不是一条单调的兑换链，它不存在类似货币面额的整除关系。立方数之间没有“进制”结构，所以你要用全局搜索或者动态规划去保证最优，而不是靠直觉。这个反例会告诉你，面试时不要一上来就写 while 循环减最大立方数，那看起来像在做题，实则已经掉进陷阱。

1.3 表面一道题，实际考三层东西

结合我看到的面试反馈，这道题可以拆出三层能力考察点：

• 第一层是建模能力。看到“最少个数”能联想到 DP 或 BFS，而不是只会暴力枚举。候选立方数很少这件事，决定了暴力 DFS 加剪枝也可能通过，但大多数人算不准上限。
• 第二层是状态设计能力。dp[i] 存什么、转移怎么枚举、初始值给多大，这三个问题能不能几秒钟内答清楚。dp[i] 表示凑出 i 需要的最少立方数个数，转移是枚举最后一枚立方数。
• 第三层是工程细节。递归深度会不会爆栈、浮点开立方有没有误差、大 n 下 O(n × m) 的量级能不能跑完，这些是代码之外的考察点。

面试官往往不在第一问停手，后面基本会跟着“打印一组具体拆法”“求有多少种拆法”“n 更大怎么办”之类的问题。所以本文把 DP、DFS、BFS 三种视角都过一遍，面试时就可以按追问方向随时切换。

2. 动态规划方案：用“最后一枚立方数”倒着搭台阶

2.1 状态定义和转移方程

DP 的标准思路是倒着想：我已经凑好了 i，那么最后一次放进来的某个立方数 c，一定满足 c ≤ i，并且在这之前已经凑好了 i - c。于是最少个数就是所有 c 里，dp[i - c] + 1 最小的那个。状态定义如下：

• dp[i]：凑出 i 这个总和所需的最少立方数个数。
• dp[0] = 0，因为 0 不需要任何数。
• 转移：dp[i] = min(dp[i - c] + 1)，其中 c 遍历所有不超过 i 的立方数。

这个转移本质上是一个完全背包问题：立方数是物品，体积是它的数值，每个物品可以用任意多次，目标是求装满容量 n 的最少物品个数。完全平方数那道题也是同一个模型，把 j^3 换成 j^2 即可。能看出这层等价关系的人，在面试里会把“为什么这样转移”讲得更顺。

2.2 工程实现：预存候选立方数而不是现算

建议先把所有不超过 n 的立方数提前存在数组里，不要在内层循环里反复算 j * j * j。原因是立方数个数 m 虽然不大，但内层循环会被执行 n × m 次，每次多一次乘法就是白给的开销。另外 j^3 用 int 存，n 稍大就可能溢出，用 long long 更稳妥。代码可以这样写：

int minCubesDP(long long n) { vector<long long> cubes; for (long long j = 1; j * j * j <= n; ++j) { cubes.push_back(j * j * j); } vector<int> dp(n + 1, n + 1); dp[0] = 0; for (int i = 1; i <= n; ++i) { for (long long c : cubes) { if (c > i) break; // cubes 递增，超过 i 就不用看了 dp[i] = min(dp[i], dp[i - c] + 1); } } return dp[n]; }

初始化 dp 数组时用 n + 1 当 INF 是安全的，因为最坏情况全用 1^3，需要 n 个立方数，所以 n + 1 一定大于任何合法答案。这也是一个小细节，面试时别人问“初始值为什么不是 INT_MAX”，你能说出这个理由，印象分会好很多。

2.3 时间空间边界：n = 0 与 10^6 的量级

复杂度是 O(n × m)，m 是不超过 n 的立方数个数，约等于 n^(1/3)。当 n = 10^6 时 m = 100，总操作量约 10^8，C++ 在一般 OJ 上可以跑进两秒左右；如果 n 到 10^7，总量到 10^9，就比较吃力了。空间上需要一个长度 n+1 的 dp 数组，O(n)。

边界条件也要聊清楚：如果题目给的是正整数，那么 n = 1 时 dp[1] = dp[0] + 1 = 1；如果非要处理 n = 0，应返回 0，dp[0] = 0 已经覆盖。这个边界虽然简单，但现场手写时很容易漏判，尤其是把 n 当成输入参数单独处理的写法。

3. DFS 方案：直观的递归拆解，以及记忆化救场

3.1 朴素 DFS 为什么指数量级爆炸

DFS 的写法非常直观。定义 dfs(left) 表示“剩余值 left 凑完所需的最少个数”，那么 dfs(0) = 0，dfs(left) = 1 + min(dfs(left - c))，其中 c 是所有不超过 left 的立方数。代码短，逻辑也顺，但如果直接照着写，朴素递归的复杂度是指数级的。

原因在于每个子问题 left 都会被重复展开很多次。递归树的分支数是 m，树的深度在最坏情况下是 n（全部用 1^3），整体状态数呈指数增长。哪怕 n = 30，朴素递归都会算得很难受。所以面试现场如果写 DFS，一定要在一分钟内意识到：这个递归是大量重算的，必须加缓存或剪枝，否则笔试数据一大就超时。

3.2 剪枝版 DFS：早期展示思路的方式

有些面试官会先让你“说说思路”，这时候可以用剪枝版 DFS 来展示你的直觉。写法是维护一个全局最优解 best，DFS 时从大到小尝试立方数，一旦当前已用个数 used 已经不小于 best，直接剪掉。因为继续搜下去不可能得到更优答案。代码大致长这样：

int best = INT_MAX; void dfs(int left, int used) { if (left == 0) { best = min(best, used); return; } if (used >= best) return; // 当前分支已经不可能超过最优 int maxJ = cbrt(left); // 最大的可能立方根 for (int j = maxJ; j >= 1; --j) { dfs(left - j * j * j, used + 1); } }

这里有个工程细节：cbrt 是浮点函数，直接转 int 可能因为浮点误差得到偏小的结果。稳妥做法是先按浮点取整，再微调：

int cubeRoot(long long x) { int r = (int)cbrt(x); while ((r + 1) * (r + 1) * (r + 1) <= x) ++r; while (r * r * r > x) --r; return r; }

这种剪枝版本在“答案比较小”的输入里跑得很快，比如 n = 8 或 n = 9，但最坏情况下仍可能退化。所以它只能作为思路演示或早期暴力版，不能当最终答案交上去。

3.3 记忆化搜到 DP：递归态和递推态的关系

把缓存加上，DFS 就变成记忆化搜索。每算完一个 left，就把结果记进 memo[left]，下次直接查表。这样每个子问题只算一遍，复杂度同样降到 O(n × m)，和 DP 的复杂度一致。

vector<int> memo; int dfsMemo(long long left) { if (left == 0) return 0; if (memo[left] != -1) return memo[left]; int res = left; // 最多用 left 个 1^3 for (long long j = 1; j * j * j <= left; ++j) { res = min(res, dfsMemo(left - j * j * j) + 1); } return memo[left] = res; }

但记忆化搜索在实际笔试中有一个坑：递归深度。最坏情况下，递归会沿着 left、left-1、left-2……一路减到 0，深度是 n，也就是 10^6 量级。默认栈空间容纳不了这么深的调用，很容易爆栈。所以我的建议是：用记忆化搜索去解释原理，证明 DFS 能优化到 O(n × m)，但最终提交或手写答案时，老老实实用循环递推的 DP。二者本质是同一个状态表，只是一个用递归填表，一个用循环填表。

4. BFS 视角：把 n 看成一张最短路径图

4.1 建图方式与分层计数

换个角度看，这道题其实是一个最短路径问题。把“当前已经凑出来的总和”看成节点，初始节点是 0。从当前和 cur 出发，可以加任意一个立方数 c，走到新节点 cur + c。问从 0 到 n 的最短距离。BFS 天然适合这种无权图，第一次扩展到 n 的层数就是最少立方数个数。代码可以这么写：

int minCubesBFS(int n) { if (n == 0) return 0; vector<bool> vis(n + 1, false); queue<pair<int, int>> q; // {当前值, 已用个数} q.push({0, 0}); vis[0] = true; while (!q.empty()) { auto [cur, step] = q.front(); q.pop(); for (long long j = 1; j * j * j <= n - cur; ++j) { int nxt = cur + j * j * j; if (nxt == n) return step + 1; if (!vis[nxt]) { vis[nxt] = true; q.push({nxt, step + 1}); } } } return -1; }

BFS 的好处是“提前终止”。如果 n 恰好是某个立方数，比如 n = 125，BFS 可能在第一步就直接返回 1，比跑满整个 DP 快得多。坏处也很明显：如果最短路很长，比如 n 很大但最优解接近 n（全是 1^3），BFS 会先把大量中间状态塞进队列，空间和时间都不好看。

4.2 三种解法的复杂度对比和取舍

把 DP、记忆化 DFS、BFS 放一起看，它们本质都是遍历同一个状态图，只是遍历顺序不同。DP 按数值从小到大填表，DFS 按递归栈深入，BFS 按层向外扩散。对比整理如下：

这里 m 仍然是不超过 n 的立方数个数。三种解法的工程实现都需要预处理 candidates，不要每次都现算立方数。能把这个对比表在脑子里过一遍，后面无论面试官怎么临时改条件，你都能快速切换解法。

5. 面试追问的答案：路径打印、方案计数与数学特例

5.1 打印一组具体的拆解方案

面试官一旦问“能不能把拆法打出来”，你就要意识到 dp 数组本身不够，得额外记录每个状态是从哪里转移过来的。维护一个 choice[i]，表示“凑出 i 时最后放进来的那个立方数”。在 dp 更新时同步记录即可：

vector<int> dp(n + 1, n + 1); vector<int> choice(n + 1, 0); dp[0] = 0; for (int i = 1; i <= n; ++i) { for (long long c : cubes) { if (c > i) break; if (dp[i - c] + 1 < dp[i]) { dp[i] = dp[i - c] + 1; choice[i] = c; // 记录最后一枚立方数 } } } int cur = n; while (cur > 0) { cout << choice[cur] << " "; cur -= choice[cur]; }

由于 choice 存的是最后一枚立方数，从 n 一路往 0 回溯，就能得到一组具体拆解。比如 n = 9，choice[9] = 1，choice[8] = 8，回溯会输出“1 8”，对应 9 = 1 + 8。这里要注意输出顺序是倒着的，但从组合角度看没有问题。

5.2 求“不区分顺序”的组合方案数

另一个高频追问是“求一共有多少种拆法”。如果直接按 dp 的思想写 cnt[i] = sum(cnt[i - c])，得到的是排列数，因为状态 i 会同时被“先加 1 再加 8”和“先加 8 再加 1”两条路径重复计数。想得到不区分顺序的组合方案数，需要用完全背包的经典写法——外层枚举物品，内层枚举容量：

vector<long long> cnt(n + 1, 0); cnt[0] = 1; for (long long c : cubes) { for (int i = c; i <= n; ++i) { cnt[i] += cnt[i - c]; } }

这个写法的原理是：每个立方数作为一类“面额”只被完整地处理一轮，加入第 k 种立方数时，只依赖之前已经处理过的立方数组合，所以同一组数不会被顺序重复计算。如果你真想求有顺序的方案数，再把循环反过来写成 cnt[i] = sum(cnt[i - c]) 即可。能分清组合和排列这两种计数的差异，面试官基本不会再问下去。

5.3 数学特例与更极限的输入

平方数和立方数在数学性质上差很多。平方数有拉格朗日四平方和定理，任何非负整数都能表示成最多四个平方数之和，所以问题有明确上界；但立方数没有这么简洁的结论，某些数需要很多个 1^3 的参与，单个数字一多就只能靠搜索或 DP。这也是为什么这道题不指望一行数学公式秒杀，而要靠最基础的算法建模。

如果面试官把 n 抬到 10^12，普通 DP 的 O(n × m) 就完全不可行了。这种时候一般是考察你知道复杂度局限在哪里，而不是真的要求现场写一个能跑的数论算法。你可以说明：候选立方数到了 10000 个左右，DP 空间和枚举规模都不现实，需要利用更多数学性质或近似剪枝，属于另一个层面的问题。能当场判断出“这个规模不能用刚才的方法”，比硬套模板重要得多。

我个人复盘这道题时最大的收获，不是死记 dp 转移方程式，而是把“最少步数/最少个数”这类问题统一理解成一个模型：状态是节点，操作是边，目标是求最短路。平方数、立方数、硬币找零，全部是同一张图上的不同边集合。以后再遇到“最少几次操作”，我先画状态图，再想遍历顺序，而不是急着套模板。这样面试时不管题目怎么变，至少思路不会跑偏。