最少立方数之和：从贪心反例到DFS剪枝与动态规划-平芜编程栈

有一道题，几乎每隔一阵子就会在模拟面试群里见到一次：给定一个正整数 n，返回最少需要多少个整数的立方数相加，才能得到 n。立方数可以重复使用。比如 n = 9 时答案是 2，因为 9 = 8 + 1；n = 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 = 1，1 = 1，答案 1。
n = 2，2 = 1 + 1，答案 2。
n = 8，8 = 8，答案 1。
n = 9，9 = 8 + 1，答案 2。
n = 35，35 = 27 + 8，答案 2。
n = 129，129 = 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 的所有立方数装进去：

vector<int> cubes; for (int i = 1; i * i * i <= n; ++i) { cubes.push_back(i * i * i); }

如果 n = 129，cubes 就是 {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: vector<int> 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; vector<int> 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] = 0
dp[1] = min(dp[0] + 1) = 1
dp[2] = min(dp[1] + 1) = 2
一直到 dp[7] = 7，因为此时可用立方数只有 1
dp[8] = min(dp[0] + 1, dp[7] + 1) = 1
dp[9] = min(dp[8] + 1, dp[1] + 1) = min(2, 2) = 2

n = 35 时：

dp[27] = 1
dp[35] = min(dp[27] + 1, dp[8] + 1, ...) = min(2, 2) = 2，因为 35 = 27 + 8

n = 129 时：

先把 64 这个立方数纳入考虑，dp[65] = dp[1] + 1 = 2
再到 i = 129 时，dp[129] = min(dp[65] + 1, dp[101] + 1, ...) = 3，来自 64 + 64 + 1

DP 不会像贪心那样走捷径，而是老老实实比较每种“最后一步取哪个立方数”的代价，所以答案一定是正确的。

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(vector<int>& coins, int amount) { vector<int> 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 = 8，cube = 8，floor 和 ceil 都是 1；但 remain = 9，cube = 8，floor 是 1，实际却需要 2 个 8 才能覆盖（不过 8+8=16>9，实际可以换小数字，但乐观下界必须是一个“不可能比真实需要的数量多”的估计）。如果取了 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 = 129：DFS 和 DP 都是毫秒级，DFS 剪枝几乎秒回。
n = 1000：答案其实只要 1 个，因为 1000 = 10^3，DFS 从最大数开始，一步就更新了 ans = 1，后面的剪枝非常猛。
n = 23：这个数比较特殊，答案是 9，因为 23 = 8 + 8 + 1 * 7，要用 9 个立方数。DFS 在这个点上也能很快结束，但如果你想测试剪枝写得是否够好，拿 23 当测试数据比 129 更合适。
n = 100000：DP 内层循环差不多要跑上千万次，但现代机器上也是很快的；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 时，步数就是答案。

核心伪代码：

queue<int> q; vector<int> 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 剪枝当作展示思考深度的加分项，两个都会，基本上能稳稳拿下这类“无限次取数求和”的题目。

最少立方数之和：从贪心反例到DFS剪枝与动态规划