有一道题几乎每隔一阵子就会在模拟面试群里见到一次给定一个正整数 n返回最少需要多少个整数的立方数相加才能得到 n。立方数可以重复使用。比如 n 9 时答案是 2因为 9 8 1n 35 时答案是 2因为 35 27 8。题目看起来很短可它是某大厂 2019 年秋招的现场算法题很多同学上来就写贪心结果挂了。原因是立方数这个“硬币系统”不满足贪心最优的性质。这篇文章我打算把这道题彻底聊透。核心是两种主流解法DFS 深度优先搜索加剪枝以及 DP 动态规划。我会把递归怎么设计、剪枝为什么能砍那么多分支、状态转移方程怎么推、面试时用什么顺序讲给面试官听全部拆开讲一遍。如果你正在准备算法面试或者想巩固一下“无限次取数求和”这类完全背包模型这篇应该能给你省不少时间。1. 题目分析与题意拆解1.1 原题描述与手算示例原题可以形式化地写成这样给定正整数 n从集合 {1, 8, 27, 64, ...} 中选若干个完全立方数允许重复使用使得它们的和恰好等于 n求最少选几个。这里有几个关键点面试时一定要先和面试官对齐立方数是正整数 i 的 i^3最小是 1所以任意正整数都一定可以用若干个 1 表示出来答案必然存在。同一个立方数可以用多次比如 8 8 1 17。题目问的是“最少的数量”不是求具体方案所以只要返回一个整数。先手算几个例子感觉一下n 11 1答案 1。n 22 1 1答案 2。n 88 8答案 1。n 99 8 1答案 2。n 3535 27 8答案 2。n 129129 64 64 1答案 3。最后一个例子很有讲究下面单独说。1.2 为什么贪心不是正解很多人第一次看到“每个数可以用多次求最小数量”会自然想到贪心每次尽量拿不超过剩余值的最大的立方数。这个策略在人民币硬币体系下是对的比如 1、5、10、20、50因为这套面额是特意设计过的。但在立方数上不成立反例就是 n 129。按贪心来做最大不超过 129 的立方数是 125拿掉之后剩下 4只能用 4 个 1总共 1 4 5 个。但最优方案是 64 64 1只有 3 个。贪心“吃了”一个 125反而毁掉了用两个 64 凑出更优解的可能。为什么贪心会失效因为立方数之间的间隔越来越大当前离目标最近的“大数”不一定是最优组合的一部分。拿 129 举例125 虽然很接近 129但它只留出了 4 的余量而 4 这个数需要 4 个 1 来填代价太高。如果用 64两个就能压到 128只差 1。可惜贪心在第一层决策时看不到这个全局组合。这就提醒我们不能用贪心得考虑搜索或动态规划。1.3 解法的整体思路这道题本质上是一个“完全背包”模型可选物品是若干立方数每个物品重量是它的值物品个数没有上限目标是刚好装满容量 n并且让物品数量最少。针对这个模型有两条主线DFS 搜索把决策过程展开成一棵递归树枚举用哪个立方数、用几个然后通过剪枝降低复杂度。优点是思路直观适合现场和面试官讨论缺点是没剪枝时是指数级的。DP 动态规划把大问题拆成小问题用最优子结构递推。优点是时间和空间复杂度可控代码短是面试中最稳的写法。两条路并不是对立的。DFS 加上记忆化本质上就变成了自顶向下的 DP而 DP 就是在用底向上的方式避免重复计算。理解了这个关系后面看代码会通透很多。2. 深度优先搜索解法从暴力枚举到剪枝优化2.1 递归函数怎么设计DFS 的核心是回答三个问题当前处理到哪个数剩余多少需要凑已经用了多少个所以递归函数可以设计成void dfs(int remain, int idx, int cnt) { // remain 表示还需要凑多少 // idx 表示当前考虑哪个下标的立方数从大到小枚举 // cnt 表示已经使用了的立方数数量 }搜索前进的方向有两种选择一是“用一次当前这个立方数”因为可以重复使用所以用完还在同一个位置继续考虑二是“跳过当前这个立方数”去考虑下一个更小的数。只要限制住“只能从大到小走不能回头”每个组合就只会被搜索到一次不会产生重复排列。预处理数组 cubes把不超过 n 的所有立方数装进去vectorint cubes; for (int i 1; i * i * i n; i) { cubes.push_back(i * i * i); }如果 n 129cubes 就是 {1, 8, 27, 64, 125}搜索时从最后一个元素 125 开始。2.2 三处剪枝的作用DFS 不剪枝在 n 稍微大一点的时候就是灾难。真正好用的剪枝有三处。第一处是“上界剪枝”如果当前 cnt 已经不小于已知最优解 ans说明就算这一步之后全部用最优方案也不可能比 ans 更好了直接返回。if (cnt 1 ans) return;注意我写的是cnt 1而不是cnt因为当前 remain 还不为 0至少还要再选一个数字所以如果cnt 1都大于等于 ans这个分支可以完全砍掉。第二处是“乐观下界剪枝”假设剩下所有空间全部用当前最大的可能立方数 cube[idx] 来填那么至少还需要ceil(remain / cube[idx])个。这是一个非常乐观的估计因为实际可能需要更多。如果乐观估计加上 cnt 仍然不够打败 ans那这个分支同样没有继续的必要。int optimistic (remain cubes[idx] - 1) / cubes[idx]; if (cnt optimistic ans) return;第三处是“当前立方数过大剪枝”如果 cubes[idx] remain那就不要在当前这个数上浪费时间了直接往更小的数走。while (idx 0 cubes[idx] remain) idx--;还有一个很实用的小优化如果当前可用的最大立方数已经退化成 1那就不需要再递归了直接ans min(ans, cnt remain)。因为剩下的数量只能全部用 1 来填这是唯一方案。2.3 完整 DFS 实现与复杂度分析把前面几点组合起来完整的 C 代码长这样class Solution { public: vectorint cubes; int ans; int minCubes(int n) { if (n 0) return 0; for (int i 1; i * i * i n; i) { cubes.push_back(i * i * i); } ans n; // 最差情况全部用 1答案是 n dfs(n, (int)cubes.size() - 1, 0); return ans; } void dfs(int remain, int idx, int cnt) { if (remain 0) { ans min(ans, cnt); return; } if (idx 0) return; // 剪枝当前数量继续走也不可能更优 if (cnt 1 ans) return; // 跳过过大的立方数 while (idx 0 cubes[idx] remain) idx--; if (idx 0) return; // 如果只能用 1 了直接结算 if (cubes[idx] 1) { ans min(ans, cnt remain); return; } // 乐观下界剪枝 int need (remain cubes[idx] - 1) / cubes[idx]; if (cnt need ans) return; // 分支1先用一次当前最大立方数 dfs(remain - cubes[idx], idx, cnt 1); // 分支2跳过当前最大立方数考虑更小的 dfs(remain, idx - 1, cnt); } };为什么递归时先走“用一次当前数”而不是先走“跳过”因为我希望尽快找到一个还算不错的方案来更新 ans。从最大数开始连续取其实就是贪心路径虽然贪心不保证最优但它能快速给 ans 一个比较小的上界这样后面的剪枝才有力。实测下来这个顺序能让剪枝效率明显提升。复杂度需要分两层说理论上这是一个指数级搜索最坏情况枚举所有组合因此不能作为大规模 n 的通用解。但加了剪枝后在 n 几千以内跑得非常快因为绝大多数分支会在“乐观下界剪枝”处被直接砍掉。面试时提一句“实际剪枝后远小于全枚举”就够了。2.4 一个容易被忽略的细节注意上面代码里我先把 ans 初始化为 n意思是“最差全部用 1”。如果 n 很大比如 1000000这个初始上界其实很宽松但配合剪枝也没有问题。还有一个细节是递归深度可能比较深最坏情况如果只有 1 可选会按照“先用1、再跳过1”的顺序一路递归。但代码里提前判断了cubes[idx] 1所以不会真的递归到 n 层深。这个优化在 n 很大时非常关键不然递归层级太深也有爆栈风险。3. 动态规划解法自底向上的最优子结构3.1 状态定义与转移方程动态规划的核心是盯住“最后一个”选择的数。假设最终凑出 i 的方案里最后一个选择的是 j^3那么在选它之前我们已经用最少的数量凑出了 i - j^3。这个前一步结果也可以看成一个独立的、同样规则的小问题于是就有了最优子结构。定义 dp[i] 表示凑出整数 i 需要的最少立方数个数。dp[0] 0。转移方程写出来就是dp[i] min( dp[i - j^3] 1 ) 其中 j^3 i这个方程看起来简单但需要想明白一个点因为每个立方数可以用无限次所以 j 的取值不需要记录“所用立方数是否已经被用过”只需要确保 j^3 不超过当前剩余空间 i。用生活类比来理解比如你要称出 i 斤的大米手里有 1 斤、8 斤、27 斤三种砝码每种任意多个。你最后一步放了一个 8 斤的砝码那在这之前秤上必须已经凑好了 i - 8 斤而且凑得越少个砝码越好。于是问题就变成了“凑 i - 8 斤”这个更小的子问题。3.2 一维 DP 代码实现实现时只需要一个一维数组从小到大遍历每个容量 i内层枚举可以用的立方数 j^3。代码很短int minCubes(int n) { if (n 0) return 0; vectorint dp(n 1, n 1); // 初始化成比答案上限更大的值 dp[0] 0; for (int i 1; i n; i) { for (int j 1; j * j * j i; j) { int cube j * j * j; dp[i] min(dp[i], dp[i - cube] 1); } } return dp[n]; }为什么初始化成 n 1而不是一个很大的数比如 INT_MAX因为如果初始化为 INT_MAX更新时执行dp[i - cube] 1可能直接溢出成负数导致结果完全错误。初始化成 n 1 就足够了因为任何正整数 n 最多用 n 个 1 就能凑出来答案不可能超过 n。内层循环的 j 为什么最多到 i 的三次根因为 j^3 i 时i - j^3变成负数没有意义。3.3 手算案例与 dp 数组演变拿 n 9 举例dp[0] 0dp[1] min(dp[0] 1) 1dp[2] min(dp[1] 1) 2一直到 dp[7] 7因为此时可用立方数只有 1dp[8] min(dp[0] 1, dp[7] 1) 1dp[9] min(dp[8] 1, dp[1] 1) min(2, 2) 2n 35 时dp[27] 1dp[35] min(dp[27] 1, dp[8] 1, ...) min(2, 2) 2因为 35 27 8n 129 时先把 64 这个立方数纳入考虑dp[65] dp[1] 1 2再到 i 129 时dp[129] min(dp[65] 1, dp[101] 1, ...) 3来自 64 64 1DP 不会像贪心那样走捷径而是老老实实比较每种“最后一步取哪个立方数”的代价所以答案一定是正确的。3.4 DFS 与 DP 的时空复杂度对比DFS 搜索 剪枝时间上最坏是指数级但剪枝后实际很好空间上主要是递归栈额外数组只有 cubes很小。DP时间复杂度 O(n * n^(1/3))因为外层 i 有 n 个状态内层枚举的立方数个数大约是 n^(1/3)空间复杂度 O(n)。放一张对比表面试时可以口述维度DFS 剪枝DP核心思想枚举组合提前砍掉不可能更优的分支记录子问题最优解自底向上最坏时间复杂度指数级O(n * n^(1/3))空间复杂度O(n^(1/3) 递归深度)O(n)编码难度略高剪枝容易写漏很短状态转移明确适合场景n 较小面试展示思考过程n 可接受 DP 数组规模求稳实际面试中我个人推荐这样表态如果 n 的范围在百万以内DP 是首选如果 n 只有几百DFS 也很好而且能体现你对搜索的理解。4. 面试视角如何从一道题展示算法能力4.1 这道题在考什么从面试官的角度这道题考察的是三件事模型识别能力是否能看出这是“无限次取数求最小数量”的完全背包问题。对贪心的警惕性是否默认贪心最优还是主动找反例。代码实现基本功递归怎么写、DP 怎么写、边界处理是否干净。如果候选人上来就写贪心面试官大概率会在 n 129 这个测试点上看到错误答案然后面试就进入“你怎么排查”的下一个难题。相反如果一开始就明确说“贪心不一定成立我举个反例129”这已经比大多数人强了。4.2 现场解说路径我建议按这样的顺序来表达复述题意确认立方数可以重复使用。举 n 8、9、35 的例子。抛出“能不能贪心”的质疑然后给反例。给 DFS 解法。讲清楚递归的三个参数以及剪枝的两种思路。自然过渡到 DP。可以说“上面 DFS 有很多重复子问题如果能记忆化其实就变成了自顶向下 DP反过来我们也可以直接用数组自底向上递推”。写完 DP 后顺手分析复杂度。这个演进路径符合“暴力 - 优化 - 最优子结构”的逻辑面试官能看出来你不是背题而是真的理解算法。4.3 需要向面试官确认的边界条件现场写代码之前有几句沟通非常加分n 的范围是多少如果 n 可能达到 10^9一维 DP 就没法用了。n 0 是否要处理虽然题目一般说正整数但防御性写出处理没关系。答案数量级会不会超过 int不会最差 n 个 1 就能凑出来所以 int 足够。这些提问不是浪费时间而是展示你对算法适用边界的敏感度。4.4 从最少硬币到完全背包的举一反三这道题其实就是完全背包求最小价值的变体。如果把它泛化一下给定一组面额 coins每种面额可以用无限次求凑出 target 需要的最少硬币数代码几乎完全一样只是把立方数数组换成 coins 数组int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); dp[0] 0; for (int i 1; i amount; i) { for (int c : coins) { if (c i) { dp[i] min(dp[i], dp[i - c] 1); } } } return dp[amount] amount 1 ? -1 : dp[amount]; }如果能主动在面试中说出“这道题和硬币找零本质一致”说明你建立了知识迁移能力。还可以补一句如果题目变成“求方案总数”一维 DP 的循环内外层顺序就要注意了因为组合数和排列数对顺序的敏感度不同但求最小值时顺序无所谓。5. 常见问题与排查技巧实录5.1 明明写对了 DP 却越界或结果异常最典型的问题是用 INT_MAX 作为 dp 数组的初始值然后执行dp[i - cube] 1。INT_MAX 加 1 会发生有符号整数溢出结果变成负数导致 dp[i] 被错误更新成一个很小的负值。解决方案有两种初始化成INT_MAX / 2加 1 后不会溢出。初始化成n 1因为答案最大也不可能超过 n。第二种更优雅也更好向面试官解释。5.2 DFS 剪枝写在哪个位置最有效很多同学写 DFS 时把剪枝一股脑堆在开头结果发现效果不理想。正确做法是动态调整位置。我的经验是先做 remain 为 0 的终点判断再做越界判断然后处理 cube 1 的特殊分支最后做乐观下界剪枝。顺序的核心原则是先排除最简单的情况再用较重度的剪枝在面对大分支时提前拦截。特别要强调的是乐观下界里要使用向上取整(remain cube - 1) / cube不要图省事写成remain / cube。比如 remain 8cube 8floor 和 ceil 都是 1但 remain 9cube 8floor 是 1实际却需要 2 个 8 才能覆盖不过 88169实际可以换小数字但乐观下界必须是一个“不可能比真实需要的数量多”的估计。如果取了 floor可能会低估这不是问题但如果取其他不保守的估计可能直接剪掉正确答案。5.3 n 0 和极端值处理如果面试官说 n 是正整数不处理 0 也没问题但写一个if (n 0) return 0;又安全又展示编码习惯。对于 DP 版本n 0 时数组长度是 1直接返回 dp[0] 0 即可。对于 DFS 版本n 0 时 cubes 数组是空的直接进入 dfs 会导致 idx -1可能出错所以必须特判。另外while (idx 0 cubes[idx] remain) idx--;这个循环后面一定要检查idx 0的情况不然下一行直接访问 cubes[idx] 就会越界。5.4 实测数据与耗时对比我在本地跑过几个有代表的 n 值给个经验感受n 129DFS 和 DP 都是毫秒级DFS 剪枝几乎秒回。n 1000答案其实只要 1 个因为 1000 10^3DFS 从最大数开始一步就更新了 ans 1后面的剪枝非常猛。n 23这个数比较特殊答案是 9因为 23 8 8 1 * 7要用 9 个立方数。DFS 在这个点上也能很快结束但如果你想测试剪枝写得是否够好拿 23 当测试数据比 129 更合适。n 100000DP 内层循环差不多要跑上千万次但现代机器上也是很快的DFS 在这么大的 n 下已经能感觉到明显变慢所以大 n 还是 DP 稳。5.5 面试复盘十分钟写哪种最稳如果面试只给十分钟我会果断先写 DP因为代码短、逻辑直、不容易出错。写完后如果时间还有再主动说“我还想到一种 DFS 写法可以配合剪枝做搜索”然后给伪代码即可。相反如果一开始就在 DFS 上纠结剪枝细节容易写得又长又绕最后可能连题目都答不完。这道题里DFS 是“加分项”DP 才是“保底项”。6. 扩展思考最少平方数、BFS 与华林问题6.1 最少平方数之和最常见的变体是把立方数换成平方数求最少的平方数之和。这个变体有一个著名的数学结论四平方定理。任何自然数都可以表示成至多四个整数平方之和。但在编程题里我们通常还是用 DP 或 BFS 来求精确答案因为数学结论能从理论上证明“不超过4”却不能直接告诉我们具体是哪几个数。转移方程完全一样dp[i] min(dp[i], dp[i - j * j] 1);这个变体在各类题库里出现的频率很高建议连立方数带平方数一起练。6.2 BFS 求最短路径还有一种思路是把这道题看成一个最短路径问题从 n 出发每一步可以减去一个立方数目标是到达 0。每条边的代价都是 1所以 BFS 第一次到达 0 时步数就是答案。核心伪代码queueint q; vectorint dist(n 1, -1); dist[n] 0; q.push(n); while (!q.empty()) { int cur q.front(); q.pop(); if (cur 0) return dist[cur]; for (int cube : cubes) { if (cube cur dist[cur - cube] -1) { dist[cur - cube] dist[cur] 1; q.push(cur - cube); } } }BFS 的好处是如果答案比较小它不需要扫描所有小于 n 的状态往往比 DP 跑得快坏处是需要额外的 dist 数组空间较大。面试时提到“这题还可以建模成最短路用 BFS 做”又是一个加分项。6.3 华林问题的一点点背景如果聊嗨了面试官可能会问“这类问题有没有数学结论”。这里可以补一句华林问题研究的正是“每个正整数最少能表示成多少个 k 次方数之和”。对于立方数有一个经典结论每个正整数都可以表示成不超过 9 个正立方数之和而 23 就是需要 9 个数的最小例子因为 23 8 8 1 * 7。注意这类数学结论只能当谈资不能作为算法依据。面试里真正的考点仍然是建模和编码能力而不是背诵定理。我在实际模拟面试中用这道题测过很多人最深的感受是面试官并不期待你三十秒写出 DP而是很看重你能不能先怀疑贪心、再给出一个能跑的搜索、最后优化成 DP。有一次候选人一直在纠结要不要背模板反而忘了先跑通最朴素版本很可惜。如果你时间有限我建议把 DP 作为保底写法把 DFS 剪枝当作展示思考深度的加分项两个都会基本上能稳稳拿下这类“无限次取数求和”的题目。 
长河君 · 2026/10/14 17:58:10 · 阅读 1.2k 最少立方数之和：从贪心反例到DFS剪枝与动态规划
有一道题几乎每隔一阵子就会在模拟面试群里见到一次给定一个正整数 n返回最少需要多少个整数的立方数相加才能得到 n。立方数可以重复使用。比如 n 9 时答案是 2因为 9 8 1n 35 时答案是 2因为 35 27 8。题目看起来很短可它是某大厂 2019 年秋招的现场算法题很多同学上来就写贪心结果挂了。原因是立方数这个“硬币系统”不满足贪心最优的性质。这篇文章我打算把这道题彻底聊透。核心是两种主流解法DFS 深度优先搜索加剪枝以及 DP 动态规划。我会把递归怎么设计、剪枝为什么能砍那么多分支、状态转移方程怎么推、面试时用什么顺序讲给面试官听全部拆开讲一遍。如果你正在准备算法面试或者想巩固一下“无限次取数求和”这类完全背包模型这篇应该能给你省不少时间。1. 题目分析与题意拆解1.1 原题描述与手算示例原题可以形式化地写成这样给定正整数 n从集合 {1, 8, 27, 64, ...} 中选若干个完全立方数允许重复使用使得它们的和恰好等于 n求最少选几个。这里有几个关键点面试时一定要先和面试官对齐立方数是正整数 i 的 i^3最小是 1所以任意正整数都一定可以用若干个 1 表示出来答案必然存在。同一个立方数可以用多次比如 8 8 1 17。题目问的是“最少的数量”不是求具体方案所以只要返回一个整数。先手算几个例子感觉一下n 11 1答案 1。n 22 1 1答案 2。n 88 8答案 1。n 99 8 1答案 2。n 3535 27 8答案 2。n 129129 64 64 1答案 3。最后一个例子很有讲究下面单独说。1.2 为什么贪心不是正解很多人第一次看到“每个数可以用多次求最小数量”会自然想到贪心每次尽量拿不超过剩余值的最大的立方数。这个策略在人民币硬币体系下是对的比如 1、5、10、20、50因为这套面额是特意设计过的。但在立方数上不成立反例就是 n 129。按贪心来做最大不超过 129 的立方数是 125拿掉之后剩下 4只能用 4 个 1总共 1 4 5 个。但最优方案是 64 64 1只有 3 个。贪心“吃了”一个 125反而毁掉了用两个 64 凑出更优解的可能。为什么贪心会失效因为立方数之间的间隔越来越大当前离目标最近的“大数”不一定是最优组合的一部分。拿 129 举例125 虽然很接近 129但它只留出了 4 的余量而 4 这个数需要 4 个 1 来填代价太高。如果用 64两个就能压到 128只差 1。可惜贪心在第一层决策时看不到这个全局组合。这就提醒我们不能用贪心得考虑搜索或动态规划。1.3 解法的整体思路这道题本质上是一个“完全背包”模型可选物品是若干立方数每个物品重量是它的值物品个数没有上限目标是刚好装满容量 n并且让物品数量最少。针对这个模型有两条主线DFS 搜索把决策过程展开成一棵递归树枚举用哪个立方数、用几个然后通过剪枝降低复杂度。优点是思路直观适合现场和面试官讨论缺点是没剪枝时是指数级的。DP 动态规划把大问题拆成小问题用最优子结构递推。优点是时间和空间复杂度可控代码短是面试中最稳的写法。两条路并不是对立的。DFS 加上记忆化本质上就变成了自顶向下的 DP而 DP 就是在用底向上的方式避免重复计算。理解了这个关系后面看代码会通透很多。2. 深度优先搜索解法从暴力枚举到剪枝优化2.1 递归函数怎么设计DFS 的核心是回答三个问题当前处理到哪个数剩余多少需要凑已经用了多少个所以递归函数可以设计成void dfs(int remain, int idx, int cnt) { // remain 表示还需要凑多少 // idx 表示当前考虑哪个下标的立方数从大到小枚举 // cnt 表示已经使用了的立方数数量 }搜索前进的方向有两种选择一是“用一次当前这个立方数”因为可以重复使用所以用完还在同一个位置继续考虑二是“跳过当前这个立方数”去考虑下一个更小的数。只要限制住“只能从大到小走不能回头”每个组合就只会被搜索到一次不会产生重复排列。预处理数组 cubes把不超过 n 的所有立方数装进去vectorint cubes; for (int i 1; i * i * i n; i) { cubes.push_back(i * i * i); }如果 n 129cubes 就是 {1, 8, 27, 64, 125}搜索时从最后一个元素 125 开始。2.2 三处剪枝的作用DFS 不剪枝在 n 稍微大一点的时候就是灾难。真正好用的剪枝有三处。第一处是“上界剪枝”如果当前 cnt 已经不小于已知最优解 ans说明就算这一步之后全部用最优方案也不可能比 ans 更好了直接返回。if (cnt 1 ans) return;注意我写的是cnt 1而不是cnt因为当前 remain 还不为 0至少还要再选一个数字所以如果cnt 1都大于等于 ans这个分支可以完全砍掉。第二处是“乐观下界剪枝”假设剩下所有空间全部用当前最大的可能立方数 cube[idx] 来填那么至少还需要ceil(remain / cube[idx])个。这是一个非常乐观的估计因为实际可能需要更多。如果乐观估计加上 cnt 仍然不够打败 ans那这个分支同样没有继续的必要。int optimistic (remain cubes[idx] - 1) / cubes[idx]; if (cnt optimistic ans) return;第三处是“当前立方数过大剪枝”如果 cubes[idx] remain那就不要在当前这个数上浪费时间了直接往更小的数走。while (idx 0 cubes[idx] remain) idx--;还有一个很实用的小优化如果当前可用的最大立方数已经退化成 1那就不需要再递归了直接ans min(ans, cnt remain)。因为剩下的数量只能全部用 1 来填这是唯一方案。2.3 完整 DFS 实现与复杂度分析把前面几点组合起来完整的 C 代码长这样class Solution { public: vectorint cubes; int ans; int minCubes(int n) { if (n 0) return 0; for (int i 1; i * i * i n; i) { cubes.push_back(i * i * i); } ans n; // 最差情况全部用 1答案是 n dfs(n, (int)cubes.size() - 1, 0); return ans; } void dfs(int remain, int idx, int cnt) { if (remain 0) { ans min(ans, cnt); return; } if (idx 0) return; // 剪枝当前数量继续走也不可能更优 if (cnt 1 ans) return; // 跳过过大的立方数 while (idx 0 cubes[idx] remain) idx--; if (idx 0) return; // 如果只能用 1 了直接结算 if (cubes[idx] 1) { ans min(ans, cnt remain); return; } // 乐观下界剪枝 int need (remain cubes[idx] - 1) / cubes[idx]; if (cnt need ans) return; // 分支1先用一次当前最大立方数 dfs(remain - cubes[idx], idx, cnt 1); // 分支2跳过当前最大立方数考虑更小的 dfs(remain, idx - 1, cnt); } };为什么递归时先走“用一次当前数”而不是先走“跳过”因为我希望尽快找到一个还算不错的方案来更新 ans。从最大数开始连续取其实就是贪心路径虽然贪心不保证最优但它能快速给 ans 一个比较小的上界这样后面的剪枝才有力。实测下来这个顺序能让剪枝效率明显提升。复杂度需要分两层说理论上这是一个指数级搜索最坏情况枚举所有组合因此不能作为大规模 n 的通用解。但加了剪枝后在 n 几千以内跑得非常快因为绝大多数分支会在“乐观下界剪枝”处被直接砍掉。面试时提一句“实际剪枝后远小于全枚举”就够了。2.4 一个容易被忽略的细节注意上面代码里我先把 ans 初始化为 n意思是“最差全部用 1”。如果 n 很大比如 1000000这个初始上界其实很宽松但配合剪枝也没有问题。还有一个细节是递归深度可能比较深最坏情况如果只有 1 可选会按照“先用1、再跳过1”的顺序一路递归。但代码里提前判断了cubes[idx] 1所以不会真的递归到 n 层深。这个优化在 n 很大时非常关键不然递归层级太深也有爆栈风险。3. 动态规划解法自底向上的最优子结构3.1 状态定义与转移方程动态规划的核心是盯住“最后一个”选择的数。假设最终凑出 i 的方案里最后一个选择的是 j^3那么在选它之前我们已经用最少的数量凑出了 i - j^3。这个前一步结果也可以看成一个独立的、同样规则的小问题于是就有了最优子结构。定义 dp[i] 表示凑出整数 i 需要的最少立方数个数。dp[0] 0。转移方程写出来就是dp[i] min( dp[i - j^3] 1 ) 其中 j^3 i这个方程看起来简单但需要想明白一个点因为每个立方数可以用无限次所以 j 的取值不需要记录“所用立方数是否已经被用过”只需要确保 j^3 不超过当前剩余空间 i。用生活类比来理解比如你要称出 i 斤的大米手里有 1 斤、8 斤、27 斤三种砝码每种任意多个。你最后一步放了一个 8 斤的砝码那在这之前秤上必须已经凑好了 i - 8 斤而且凑得越少个砝码越好。于是问题就变成了“凑 i - 8 斤”这个更小的子问题。3.2 一维 DP 代码实现实现时只需要一个一维数组从小到大遍历每个容量 i内层枚举可以用的立方数 j^3。代码很短int minCubes(int n) { if (n 0) return 0; vectorint dp(n 1, n 1); // 初始化成比答案上限更大的值 dp[0] 0; for (int i 1; i n; i) { for (int j 1; j * j * j i; j) { int cube j * j * j; dp[i] min(dp[i], dp[i - cube] 1); } } return dp[n]; }为什么初始化成 n 1而不是一个很大的数比如 INT_MAX因为如果初始化为 INT_MAX更新时执行dp[i - cube] 1可能直接溢出成负数导致结果完全错误。初始化成 n 1 就足够了因为任何正整数 n 最多用 n 个 1 就能凑出来答案不可能超过 n。内层循环的 j 为什么最多到 i 的三次根因为 j^3 i 时i - j^3变成负数没有意义。3.3 手算案例与 dp 数组演变拿 n 9 举例dp[0] 0dp[1] min(dp[0] 1) 1dp[2] min(dp[1] 1) 2一直到 dp[7] 7因为此时可用立方数只有 1dp[8] min(dp[0] 1, dp[7] 1) 1dp[9] min(dp[8] 1, dp[1] 1) min(2, 2) 2n 35 时dp[27] 1dp[35] min(dp[27] 1, dp[8] 1, ...) min(2, 2) 2因为 35 27 8n 129 时先把 64 这个立方数纳入考虑dp[65] dp[1] 1 2再到 i 129 时dp[129] min(dp[65] 1, dp[101] 1, ...) 3来自 64 64 1DP 不会像贪心那样走捷径而是老老实实比较每种“最后一步取哪个立方数”的代价所以答案一定是正确的。3.4 DFS 与 DP 的时空复杂度对比DFS 搜索 剪枝时间上最坏是指数级但剪枝后实际很好空间上主要是递归栈额外数组只有 cubes很小。DP时间复杂度 O(n * n^(1/3))因为外层 i 有 n 个状态内层枚举的立方数个数大约是 n^(1/3)空间复杂度 O(n)。放一张对比表面试时可以口述维度DFS 剪枝DP核心思想枚举组合提前砍掉不可能更优的分支记录子问题最优解自底向上最坏时间复杂度指数级O(n * n^(1/3))空间复杂度O(n^(1/3) 递归深度)O(n)编码难度略高剪枝容易写漏很短状态转移明确适合场景n 较小面试展示思考过程n 可接受 DP 数组规模求稳实际面试中我个人推荐这样表态如果 n 的范围在百万以内DP 是首选如果 n 只有几百DFS 也很好而且能体现你对搜索的理解。4. 面试视角如何从一道题展示算法能力4.1 这道题在考什么从面试官的角度这道题考察的是三件事模型识别能力是否能看出这是“无限次取数求最小数量”的完全背包问题。对贪心的警惕性是否默认贪心最优还是主动找反例。代码实现基本功递归怎么写、DP 怎么写、边界处理是否干净。如果候选人上来就写贪心面试官大概率会在 n 129 这个测试点上看到错误答案然后面试就进入“你怎么排查”的下一个难题。相反如果一开始就明确说“贪心不一定成立我举个反例129”这已经比大多数人强了。4.2 现场解说路径我建议按这样的顺序来表达复述题意确认立方数可以重复使用。举 n 8、9、35 的例子。抛出“能不能贪心”的质疑然后给反例。给 DFS 解法。讲清楚递归的三个参数以及剪枝的两种思路。自然过渡到 DP。可以说“上面 DFS 有很多重复子问题如果能记忆化其实就变成了自顶向下 DP反过来我们也可以直接用数组自底向上递推”。写完 DP 后顺手分析复杂度。这个演进路径符合“暴力 - 优化 - 最优子结构”的逻辑面试官能看出来你不是背题而是真的理解算法。4.3 需要向面试官确认的边界条件现场写代码之前有几句沟通非常加分n 的范围是多少如果 n 可能达到 10^9一维 DP 就没法用了。n 0 是否要处理虽然题目一般说正整数但防御性写出处理没关系。答案数量级会不会超过 int不会最差 n 个 1 就能凑出来所以 int 足够。这些提问不是浪费时间而是展示你对算法适用边界的敏感度。4.4 从最少硬币到完全背包的举一反三这道题其实就是完全背包求最小价值的变体。如果把它泛化一下给定一组面额 coins每种面额可以用无限次求凑出 target 需要的最少硬币数代码几乎完全一样只是把立方数数组换成 coins 数组int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); dp[0] 0; for (int i 1; i amount; i) { for (int c : coins) { if (c i) { dp[i] min(dp[i], dp[i - c] 1); } } } return dp[amount] amount 1 ? -1 : dp[amount]; }如果能主动在面试中说出“这道题和硬币找零本质一致”说明你建立了知识迁移能力。还可以补一句如果题目变成“求方案总数”一维 DP 的循环内外层顺序就要注意了因为组合数和排列数对顺序的敏感度不同但求最小值时顺序无所谓。5. 常见问题与排查技巧实录5.1 明明写对了 DP 却越界或结果异常最典型的问题是用 INT_MAX 作为 dp 数组的初始值然后执行dp[i - cube] 1。INT_MAX 加 1 会发生有符号整数溢出结果变成负数导致 dp[i] 被错误更新成一个很小的负值。解决方案有两种初始化成INT_MAX / 2加 1 后不会溢出。初始化成n 1因为答案最大也不可能超过 n。第二种更优雅也更好向面试官解释。5.2 DFS 剪枝写在哪个位置最有效很多同学写 DFS 时把剪枝一股脑堆在开头结果发现效果不理想。正确做法是动态调整位置。我的经验是先做 remain 为 0 的终点判断再做越界判断然后处理 cube 1 的特殊分支最后做乐观下界剪枝。顺序的核心原则是先排除最简单的情况再用较重度的剪枝在面对大分支时提前拦截。特别要强调的是乐观下界里要使用向上取整(remain cube - 1) / cube不要图省事写成remain / cube。比如 remain 8cube 8floor 和 ceil 都是 1但 remain 9cube 8floor 是 1实际却需要 2 个 8 才能覆盖不过 88169实际可以换小数字但乐观下界必须是一个“不可能比真实需要的数量多”的估计。如果取了 floor可能会低估这不是问题但如果取其他不保守的估计可能直接剪掉正确答案。5.3 n 0 和极端值处理如果面试官说 n 是正整数不处理 0 也没问题但写一个if (n 0) return 0;又安全又展示编码习惯。对于 DP 版本n 0 时数组长度是 1直接返回 dp[0] 0 即可。对于 DFS 版本n 0 时 cubes 数组是空的直接进入 dfs 会导致 idx -1可能出错所以必须特判。另外while (idx 0 cubes[idx] remain) idx--;这个循环后面一定要检查idx 0的情况不然下一行直接访问 cubes[idx] 就会越界。5.4 实测数据与耗时对比我在本地跑过几个有代表的 n 值给个经验感受n 129DFS 和 DP 都是毫秒级DFS 剪枝几乎秒回。n 1000答案其实只要 1 个因为 1000 10^3DFS 从最大数开始一步就更新了 ans 1后面的剪枝非常猛。n 23这个数比较特殊答案是 9因为 23 8 8 1 * 7要用 9 个立方数。DFS 在这个点上也能很快结束但如果你想测试剪枝写得是否够好拿 23 当测试数据比 129 更合适。n 100000DP 内层循环差不多要跑上千万次但现代机器上也是很快的DFS 在这么大的 n 下已经能感觉到明显变慢所以大 n 还是 DP 稳。5.5 面试复盘十分钟写哪种最稳如果面试只给十分钟我会果断先写 DP因为代码短、逻辑直、不容易出错。写完后如果时间还有再主动说“我还想到一种 DFS 写法可以配合剪枝做搜索”然后给伪代码即可。相反如果一开始就在 DFS 上纠结剪枝细节容易写得又长又绕最后可能连题目都答不完。这道题里DFS 是“加分项”DP 才是“保底项”。6. 扩展思考最少平方数、BFS 与华林问题6.1 最少平方数之和最常见的变体是把立方数换成平方数求最少的平方数之和。这个变体有一个著名的数学结论四平方定理。任何自然数都可以表示成至多四个整数平方之和。但在编程题里我们通常还是用 DP 或 BFS 来求精确答案因为数学结论能从理论上证明“不超过4”却不能直接告诉我们具体是哪几个数。转移方程完全一样dp[i] min(dp[i], dp[i - j * j] 1);这个变体在各类题库里出现的频率很高建议连立方数带平方数一起练。6.2 BFS 求最短路径还有一种思路是把这道题看成一个最短路径问题从 n 出发每一步可以减去一个立方数目标是到达 0。每条边的代价都是 1所以 BFS 第一次到达 0 时步数就是答案。核心伪代码queueint q; vectorint dist(n 1, -1); dist[n] 0; q.push(n); while (!q.empty()) { int cur q.front(); q.pop(); if (cur 0) return dist[cur]; for (int cube : cubes) { if (cube cur dist[cur - cube] -1) { dist[cur - cube] dist[cur] 1; q.push(cur - cube); } } }BFS 的好处是如果答案比较小它不需要扫描所有小于 n 的状态往往比 DP 跑得快坏处是需要额外的 dist 数组空间较大。面试时提到“这题还可以建模成最短路用 BFS 做”又是一个加分项。6.3 华林问题的一点点背景如果聊嗨了面试官可能会问“这类问题有没有数学结论”。这里可以补一句华林问题研究的正是“每个正整数最少能表示成多少个 k 次方数之和”。对于立方数有一个经典结论每个正整数都可以表示成不超过 9 个正立方数之和而 23 就是需要 9 个数的最小例子因为 23 8 8 1 * 7。注意这类数学结论只能当谈资不能作为算法依据。面试里真正的考点仍然是建模和编码能力而不是背诵定理。我在实际模拟面试中用这道题测过很多人最深的感受是面试官并不期待你三十秒写出 DP而是很看重你能不能先怀疑贪心、再给出一个能跑的搜索、最后优化成 DP。有一次候选人一直在纠结要不要背模板反而忘了先跑通最朴素版本很可惜。如果你时间有限我建议把 DP 作为保底写法把 DFS 剪枝当作展示思考深度的加分项两个都会基本上能稳稳拿下这类“无限次取数求和”的题目。