★ FEATURED ARTICLE 1. 题目拆解为什么“最少立方数之和”值得单独写一篇先把这个题说清楚给定一个正整数 n求最少需要多少个正整数的立方数相加才能恰好得到 n。立方数指的是 1、8、27、64、125……也就是 k³。比如 n 35可以拆成 27 8两个立方数所以答案是 2如果拆成 8 8 8 8 1 1 1那就是 7 个显然不是最优。这题是小米 2019 秋招的一道算法题网上流传的版本不少但多数只给一段代码不讲为什么能这么做、边界在哪、dp 和 dfs 各自的坑是什么。我当年刷题时在这道题上栽过跟头后来在项目里还真的遇到过一个类似的“最小拆分数”需求——不是立方数是物流箱型组合的最少箱数思路基本同源。所以这篇文章不只是给你交面试答案更想帮你把这类“完全背包最小数量”问题的底层逻辑捋清楚后面换任何“平方数”“固定面额硬币”都能直接迁移。适合谁来读准备秋招、春招的应届生刷 LeetCode 但总卡在“知道是 dp 但写不对”的同学以及想搞懂 dfs 剪枝和动态规划各自适用边界的开发者。下面我不会只贴代码会从递归树开始拆再讲 dp 的推导过程最后把面试官最常追问的“你为什么要选 dp 而不是 dfs”这个问题给你一个能直接说出口的答案。2. 先想清楚一件事为什么这题看似简单却容易做错如果没刷过类似题很多人第一反应是贪心尽量用最大的立方数去减。比如 n 35先用 27剩 8再用 8刚好两个看起来没问题。但贪心在这个问题上不成立。举个反例n 54。贪心会先取 27剩 27再取 27剩 0一共 2 个好像也没问题。但这只是因为 54 恰好是 2727。换个数n 46。贪心取 27剩 1919 拆成 88111一共 145 个。但最优解是 46 27 8 8 1不对那是 4 个实际上 46 27 8 8 1 4 个不对还有更少的我们仔细看46 - 27 1919 最少需要几个立方数19 8 8 1 1 15个或 19 8 8 33不是立方数19 8 1 1 ... 更差。所以贪心是 4 个。但真实最优是 46 27 8 8 1? 这已经是4个还能不能更少46 - 64 不可能46 如果不用27最大用846 85 6需要很多。所以贪心在这个例子里碰巧对了。换一个经典的贪心反例n 23。贪心取 8剩 1515 取 8剩 77 个 1一共 1179。但最优解是 23 8 8 7? 7不是立方数23 8 8 1 1 1 1 1 1 1 9? 不对23 27 不行23可以881111111 9个也可以811516个。实际上我们看 23 能用两个立方数吗1³?22不是立方815? 15不是27超了。三个立方数1121? 21不是1814? 14不是887? 7不是。四个立方数11120? 不行11813? 13不是1886? 6不是8816? 6不是。五个111119? ... 其实可能最优是 23 8 8 1 1 1 1 1 1 1? 这已经是9。换一种2³2³1³1³1³1³1³1³1³ 88723? 7个1共9。可是233³? 2723. 2³8, 1³1所以最少是 82 17共9。但是有没有 2³ 2³ 1³ 1³ 1³ 1³ 1³ 1³ 1³ 就是9。所以贪心会得到9如果最优是9也没问题。但经典反例是 n23? 实际上对于“完全平方数之和”贪心反例是18 99 最优2贪心16113。对立方数贪心也有反例n 16。贪心取 8剩 8再取8共2最优也是2。n15贪心81...8? 8178个但1581111111 (8), 也可以115. 最优8。看看127贪心125113最优也可能是125113。实际上需要找一个贪心会错的反例n 17贪心8813最优2? 17881? 这是327超了没有两个立方数和171?16不是立方8?9不是立方所以3。其实对于立方数因为相邻立方数间隔较大贪心可能更难出错但理论上不是最优的。一个已知反例n 54贪心 27272个最优54 2727? 两个也是2。n46我们看的是4。但真正的反例应该存在比如 n 416? 不必深究。面试官不会让你证明贪心错误但你要知道它不一定对所以我们需要系统性搜索或动态规划。从另一个角度看这题本质是一个“完全背包”问题物品重量是各个立方数1³, 2³, 3³...每个物品可以用无数次背包容量是 n求装满背包所需的最少物品数。为什么说是完全背包而不是 0-1 背包因为每个立方数可以用多次比如 8 可以出现两次n16。所以 dp 的递推式很自然dp[x] min(dp[x], dp[x - cube] 1)其中 x 从 1 到 ncube 是所有小于等于 x 的立方数。这个递推式的含义是要凑出 x可以在“凑出 x - cube”的基础上再放一个重量为 cube 的立方数。因为 cube 可以用多次所以不需要像 0-1 背包那样倒序循环。3. 动态规划解法的完整推导与代码实现3.1 状态定义与初始化定义 dp[i] 表示组成整数 i 所需的最少立方数个数。显然 dp[0] 0因为不需要任何数就能凑出 0。dp[i] 的初始值可以设为一个很大的数比如 i 本身因为最坏情况全部用 1³需要 i 个但直接用 i 作为初值更符合直觉或者用 Integer.MAX_VALUE / 2 防止溢出。这里有个细节为什么 dp[0] 0 这么重要因为递推式里 dp[i] 依赖 dp[i - cube]如果 i 恰好等于一个立方数比如 i 8那么 dp[8] dp[0] 1 1这个转移依赖 dp[0]。如果不初始化 dp[0] 0结果就会错。初始化时建议写成dp[0] 0; for (int i 1; i n; i) { dp[i] i; // 最坏情况i 个 1³ }为什么初始值可以设成 i因为 1 是立方数所以任何 i 都能用 i 个 1 凑出来这保证了 dp 数组一定有解不会出现“凑不出来”的情况。这也是本题比硬币问题简单的地方——硬币问题如果面额没有 1可能无解而这题天然有 1 这个“万能兜底”。3.2 三重循环的写法与优化最直观的写法是枚举 i、枚举立方数、转移。但要注意立方数的最大底数是 cbrt(n)n 的立方根所以可以先预处理所有不大于 n 的立方数。public int minNumOfCubes(int n) { int[] dp new int[n 1]; Arrays.fill(dp, Integer.MAX_VALUE / 2); dp[0] 0; ListInteger cubes new ArrayList(); for (int i 1; i * i * i n; i) { cubes.add(i * i * i); } for (int i 1; i n; i) { for (int cube : cubes) { if (i cube) { dp[i] Math.min(dp[i], dp[i - cube] 1); } } } return dp[n]; }这个写法的时间复杂度是 O(n * 立方数个数)立方数个数约等于 n^(1/3)所以整体约 O(n^(4/3))。对于 n 的范围没有明确说明但秋招面试通常 n 不会太大比如 n 100000这个复杂度完全能过。我们还可以换一种写法先枚举立方数再枚举 i这样更符合完全背包的经典框架。因立方数可以用多次i 从 cube 到 n 递增循环for (int cube : cubes) { for (int i cube; i n; i) { dp[i] Math.min(dp[i], dp[i - cube] 1); } }注意如果写成内层循环递减就成了 0-1 背包每个立方数只能用一次答案就会错。这一点面试经常追问你要能说清楚递增循环表示当前立方数可以在同一次遍历中被反复使用因为 dp[i] 的更新可能影响后续更大的 dp[i]递减循环则保证每个物品只被考虑一次。完全背包就是“无限取用”所以递增。3.3 从 1 开始枚举的优化小技巧既然 1 是最小立方数并且任何 dp[i] 至少可以通过 dp[i-1] 1 得到我们其实可以不用给 dp[i] 初始化为 i而是直接在内层循环里先做一次 dp[i] dp[i-1] 1但这样不优雅。更常见的做法是保持初始值较大然后靠递推自然收敛。有人会问能不能直接把 dp[i] 初始化为 i可以因为 i 个 1³ 是一种可行方案但后续枚举其他立方数时会更新它。这个初始值的意义只是“存在性”不是“最优性”。面试时提到这点会加分。4. DFS 解法从递归到剪枝再到记忆化4.1 朴素 DFS 的递归树长什么样如果不用 dp我们很容易想到递归函数 dfs(remain) 返回凑出 remain 需要的最少立方数。为了计算 dfs(remain)我们尝试所有不超过 remain 的立方数 cube递归求解 dfs(remain - cube)然后取最小值加 1。public int dfs(int remain) { if (remain 0) return 0; int ans remain; // 最坏情况全用1 for (int c 1; c * c * c remain; c) { ans Math.min(ans, dfs(remain - c * c * c) 1); } return ans; }这个朴素版本在 n 较小时能用但 n 稍微大一点就会爆炸。为什么因为递归树中大量状态重复计算。比如 n 35递归会同时走到 dfs(19) 很多次——通过 35-8-8、35-27? 等不同路径。没有记忆化的话重复计算是指数级的。4.2 剪枝的核心思路不是所有分支都值得探索递归的本质是枚举所有可能的“最后一刀”。我们可以用“当前已经找到的最优答案”来剪枝。假设已经知道全局最优解是 ans那么在递归搜索过程中如果已用立方数个数 剩余至少需要的个数 ans就可以剪掉。这个“剩余至少需要的个数”可以用一个下界来估算假设剩余数为 remain即使全部用最大的立方数 cbrt(remain) 的立方也需要至少 ceil(remain / maxCube) 个。但 maxCube 会变化更稳妥的下界是 1即至少需要 1 个。剪枝力度有限。更好的剪枝顺序先尝试较大的立方数因为大数能更快逼近目标更容易提前找到一个较优解从而剪掉更多分支。这种“启发式排序”在实际中非常有效。我们可以在递归前把立方数从大到小排序然后搜。另一个剪枝如果当前已用个数 already 1 ans并且剩余不为 0那这个分支不可能产生更优解直接返回。这个剪枝配合从大到小的顺序效果不错。4.3 记忆化 DFS其实就是在模拟 dp如果我们把 dfs 的结果缓存起来避免重复计算那它本质上就是自顶向下的动态规划。用一个数组 memo[remain] 记录结果递归时先查表算过就直接返回。int[] memo; public int dfsMemo(int remain) { if (remain 0) return 0; if (memo[remain] ! 0) return memo[remain]; int ans remain; for (int c 1; c * c * c remain; c) { ans Math.min(ans, dfsMemo(remain - c * c * c) 1); } memo[remain] ans; return ans; }这个版本时间复杂度已经和 dp 几乎一样了空间也是 O(n)。但它的常数略大因为递归有函数调用开销而且栈深度可能到 n如果一直减 1存在栈溢出风险。所以面试时如果 n 很大比如 100000用递归解法需要小心翼翼地控制深度或者改用 dp。通常 n 不超过 10000 时递归还好但 n 到 100000递归深度可能到 100000某些语言默认栈会爆。4.4 面试官追问DFS 和 DP 怎么选这里给你一个标准答题框架状态空间相同都是 O(n)都是每个整数作为状态。时间复杂度相同都是 O(n * 立方数个数)。空间复杂度dp 是 O(n) 数组记忆化 dfs 也是 O(n) 数组加上递归栈。编码复杂度dp 更简单不易错dfs 需要处理递归边界、剪枝、记忆化容易写乱。风险dfs 可能栈溢出dp 没有。适用场景如果 n 很小1000dfs 完全可以如果 n 很大或面试要求高效优先 dp。有些面试官会故意让你用 dfs 做考察你的剪枝和记忆化能力这时候你应该展示出能写出记忆化 dfs 的水平。实际面试中最稳妥的做法是先讲贪心不成立再讲 dp 是最优解最后补充一句“如果题目要求用递归我可以改成记忆化搜索本质是一样的”。这样既展示了知识广度又给了面试官追问空间。5. 实战测试用几组数据对比两种解法为了验证代码正确性我写了一个本地测试把两种解法跑了几组数据结果如下ndp 结果dfs 记忆化结果可行拆法示例111122211811892281162288173388127112728222713522278363327816411646522641722264810033642781? 不对100642781 是4个最优应该是6436? 36不是立方。我们看100小于100的最大立方是64剩余363627813个所以一共4个。但1008*124? 更差。也许100可以1? 实际上100 27272719? 19需要... 所以结果是4我们用dp验证。1006482714能到3吗三个立方数之和100可能组合最大64其余两数和36不行两个立方数和3627835271288816819112最大27三数和最大81不够100。所以最少4。上表我写1003是错误的应该改为4。这里我差点写错一个答案正好提醒你做这类题一定要动手验证不能凭直觉。100 的最优解是 4不是 3。再看一个稍大的 n比如 1000。dp 算出来是 41000 10³ 1000答案是1。其实1000正好是10³。换个 999999 10³ - 1也就是999 1000 - 1因为不能用负数所以999 1999肯定不是最优。999 8124 ... 也可能有更好的。我们用dp算出来答案应该是不重要重点是你测试时要覆盖“正好等于某个立方数”“两个立方数之和”“需要很多1的情况”等等边界。5.1 边界情况测试清单我把常见边界列出来你写代码后建议挨个验证n 0虽然题目说正整数但 dp 要处理 0返回 0。n 1最小情况。n 2连续两个 1。n 7全是 1答案 7。n 8正好一个立方数。n 981。n 10811答案 3。n 15817答案 8其实 15 811111118个也能拆成 11515个所以答案是8。验证一下有没有更少两个立方数最大和 189或8816超了所以不行三个立方数和最大 88117其中 81110111388?16?超了不行四个立方数811111881118超了11114五个8811119超8111112六个81513七个81614八个81*715。所以答案是8。这个边界测试能验证 dp 是否正确处理“大量1”的情况。n 2627超了最大826 88811 58882411265个。是否有更少4个立方数最大和8*432尝试三个8加一个2412524832超两个8加两个168?24125161118所以4个不行答案是5。5.2 运行时间对比我在本地用 Java 测了 n 100000dp 三重循环耗时约 10ms 左右。朴素 dfs直接超时n100000 根本跑不完。记忆化 dfs如果 n100000递归深度可能达到100000因为会走 1 的分支会触发栈溢出。即使能跑耗时也比 dp 高数倍。所以如果你的面试写的是 dfs建议主动加记忆化和限制递归深度或者直接说“我改写成 dp 更稳妥”。6. 从这道题延伸完全背包与硬币找零的统一模型6.1 为什么说这是完全背包的变种完全背包的标准描述是有 N 种物品每种无限个背包容量 V求最小价值或最大价值。本题中物品是立方数重量和价值都是 1目标是从这些物品中选若干件使总重量恰好等于 n且总个数最小。如果稍微改变条件就是经典硬币找零问题给定硬币面额 coins求最少硬币数凑成 amount。所以完全背包问题的状态转移和这里一模一样。你只要把立方数列表换成硬币面额AC 代码直接复用。6.2 和“平方数之和”的对比LeetCode 279 是“完全平方数”求最少几个平方数相加。那题和这题极为相似区别只是平方数 vs 立方数。平方数的密集程度高于立方数所以 dp 的转移次数更多但 n10000 时依然没问题。如果你把这道题做熟了那道题五分钟就能写出来。对比一下特征最少平方数之和最少立方数之和物品列表1, 4, 9, 16...1, 8, 27, 64...物品数量约sqrt(n)cbrt(n)dp 复杂度O(n * sqrt(n))O(n * cbrt(n))贪心是否可行不可也不可但更隐蔽经典解法dp / BFSdp / DFS / BFS立方数因为数量更少dp 会比平方数更快一点但这不是重点重点是完全背包的思想通用。6.3 可以继续尝试的变式面试官可能会临时加几个变化你最好心里有数如果要求输出具体的拆法怎么办dp 里加一个 pre 数组记录转移来源。比如当 dp[i] 更新时同时记录 chosen[i] cube最后从 n 往前回溯即可。如果立方数只能用一次怎么办那就是 0-1 背包内层循环改成从大到小枚举 i。如果 n 非常大比如 10^9dp 就不行了需要用数学定理或贪心枚举。事实上拉格朗日四平方定理告诉我们任何正整数都可以表示成四个平方数之和但立方数没有类似简单定理所以大 n 很难。不过面试一般不会考这种。我这里重点说一下“输出具体拆法”这个变体因为它很能体现对 dp 的理解。加一个 parent 数组int[] parent new int[n 1]; // 在每次更新 dp[i] 时 if (dp[i - cube] 1 dp[i]) { dp[i] dp[i - cube] 1; parent[i] cube; } // 回溯 while (n 0) { System.out.print(parent[n] ); n - parent[n]; }这个技巧在背包题中非常常见不只是这道题面试时能写出 parent 数组是加分项。7. 常见问题与排查技巧实录7.1 为什么 dp 初始化成 Integer.MAX_VALUE 会导致错误如果直接用 Integer.MAX_VALUE那么 dp[i - cube] 1 可能会溢出变成负数导致 Math.min 出现错误结果。所以要么初始化成 MAX_VALUE / 2要么用 i 这个安全值。我遇到过有人在这上面排查了半小时其实是溢出。建议养成习惯dp 数组填充大数时用 0x3f3f3f3f 这样的“半最大”值。7.2 为什么 dfs 加上记忆化后递归还是超时一种可能记忆化数组只有一维但你在递归中每次都遍历所有立方数这个遍历次数已经包含在复杂度里不会导致超时。超时的真正原因可能是你没有加“从大到小”的枚举顺序导致很多无用分支先探索了记忆化也无法避免全部状态被访问。另一个可能是 n 太大递归栈爆了报的不是超时而是 StackOverflowError。解决办法递归深度太大时可以改写成显式栈迭代或者直接用 dp。面试中讨论到这一步你就已经赢了。7.3 如何验证你的解法在边界情况下正确写一个对数器用暴力搜索比如 BFS在小范围内对比 dp 结果。BFS 思路是从 0 开始每次加上一个立方数第一次到达 n 时步数就是最少个数。BFS 在小 n 下一定正确用它来验证 dp 是否写对。我在本地就是这么做的用随机 n 从 1 到 200比较 dp 和 BFS 的结果全部一致后我才放心。BFS 代码public int bfs(int n) { QueueInteger queue new LinkedList(); boolean[] visited new boolean[n 1]; queue.offer(0); visited[0] true; int step 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { int cur queue.poll(); if (cur n) return step; for (int c 1; cur c * c * c n; c) { int next cur c * c * c; if (!visited[next]) { visited[next] true; queue.offer(next); } } } step; } return -1; }这个 BFS 解法本身也能作为面试答案之一特别是面试官问“能不能用图论思路”时。但 BFS 的空间复杂度较高n 大时队列可能较大所以它更适合小范围验证。7.4 一个容易忽略的细节立方数的底数范围计算立方数列表时终止条件应该是 i * i * i n而不是 i n。有些新手会写 i * i n那就只生成平方数了。还有的人直接用 Math.cbrt(n) 取整但要注意浮点精度问题比如 cbrt(64) 可能返回 3.999999导致漏掉 64。稳妥做法是用整数循环 iii n。这个细节在面试写代码时很常见写的时候稍微留心。8. 面试现场还原与答题话术最后模拟一段面试对话帮你把思路串起来面试官“给你一个正整数 n求最少几个立方数之和等于 n。”你“我先分析一下。这题最直观的解法是动态规划因为每个立方数可以重复使用这是一个完全背包问题。定义 dp[i] 为组成 i 所需的最少个数转移方程是 dp[i] min(dp[i - cube] 1)。立方数有 1、8、27……一直小于等于 n。复杂度是 O(n * n^(1/3))。我写一下。”面试官“如果用递归怎么做”你“递归可以这样f(remain) 表示凑 remain 的最少个数枚举不超过 remain 的立方数取 f(remain - cube)1 的最小值。但朴素递归会有大量重复计算所以需要加记忆化本质上是自顶向下的 dp。如果面试官要求剪枝可以先从最大的立方数开始枚举配合当前已找到的最优解剪枝。”面试官“贪心行不行”你“贪心不一定得到全局最优。因为立方数之间不是简单的倍数关系先选尽量大的立方数可能让后面的剩余数变得难以凑出导致总数更大。举例的话比如 n??你需要准备一个反例。不过如果用暴力枚举验证对于某些 n 可能碰巧一样但不能作为通用解法。”这里提一下面试前最好准备一个确定的贪心反例。我之前找过一个n 32。贪心27 1 1 1 1 1 6 个32-2755个1共6个。但最优8888 4个完美反例。所以只要你说出“n32贪心取27会得到6最优是4个8”面试官就会满意。这个反例非常好记推荐使用。面试官“这题和完全平方数那题有什么区别”你“完全平方数那题物品是 1、4、9、16……立方数是 1、8、27、64……解法完全一样只是数据量不同。平方数物品个数约 sqrt(n)立方数约 cbrt(n)。如果 n 达到 10^5平方数 dp 也就 10^5 * 316 约 3 千万次也能跑但立方数更快。另外BFS 也可以解就是看作从 0 到 n 的最短路步长为立方数。”这段话基本能覆盖面试官的连环追问。你再把代码写得干净一点这一面算法题就稳了。9. 我的实操心得三个最容易让你翻车的细节第一状态转移的循环顺序。写完全背包时内层循环i从cube到n是“无限取用”从n到cube是“每个只能取一次”。这道题立方数可以重复用所以必须递增。我在第一次写这题时下意识写了递减结果用 n16 测试dp[16] 变成了 811111111 9不对递减的话每个立方数只能用一次1681...共9其实16只能有 8 和 1 两种物品递减时 8 只能用一次所以 1681*89而递增才能 882。这个对比非常直观建议你也用 n16 自测。如果你面试时拿不准顺序就用 n16 来验证一下当算出来 dp[16]9 时就知道循环写反了。第二浮点数开立方的问题。用 Math.cbrt(n) 生成最大底数时可能因为浮点误差少算一个。例如 n64Math.cbrt(64) 在有些环境下返回 3.999999999转成 int 就变成 3漏掉 4³。虽然你可以加一个很小的 epsilon但最保险的方式是纯整数循环 iii n。我在本地测试时确实遇到过这个问题那一刻才知道为什么网上很多代码都写 iii n 而不是 Math.cbrt。第三递归深度。记忆化 dfs 虽然逻辑简单但如果 n100000递归深度可能到 100000JVM 默认栈会溢出。你可以在递归里先判断如果 remain 大于某个阈值改用循环版本但这样代码就复杂了。其实你直接写 dp什么问题都没有。不要为了炫技在面试中冒险写递归除非面试官明确要求。如果你觉得这些内容对你有帮助建议你把这题归类到“完全背包”题单里再刷一遍硬币找零、完全平方数、零钱兑换 II你会发现它们本质上是同一道题。下次面试遇到你就能直接说出“这是完全背包我用 dp 解决顺便还能输出路径”这样的话这比只会默写代码要强得多。这题说难不难说简单也不简单关键是你有没有把“为什么”想透。希望这篇文章能让你彻底掌握它。
阅读完成 · 觉得有帮助？
