整数拆分问题全解：动态规划、数学优化与三语言实现-北京尧图网络

3月15日滴滴春招在线测评第一题题目名只有两个字划分。我拿到题面的时候愣了一下——没有背景故事、没有复杂数据结构就一个正整数n要拆成至少两个正整数的和让乘积最大。做过相关题库的朋友应该已经笑了没错就是那道整数拆分。但春招第一题放在这里并不是让你背答案而是考察从特殊到一般的数学归纳能力以及三种主流语言的基本功。这篇文章我会从题意复述、暴力递归、动态规划、数学优化到Java/C/Python代码逐个拆开再把我在实际调试中踩过的边界坑全部摊开讲。无论你是准备暑期实习、还是春招补录这道题都值得吃透。1. 题面还原与第一题的考点陷阱1.1 我记忆中的题目描述题目给了一个整数n要求把n拆分成至少两个正整数的和然后计算这些正整数相乘的乘积输出能得到的最大乘积。举个例子输入 n 2只能拆成 11乘积是 1。输入 n 3可以拆成 12乘积是 2如果拆成 111乘积就是 1所以答案是 2。输入 n 4拆成 22 乘积是 4拆成 13 乘积是 3答案是 4。输入 n 10最优拆法是 334乘积是 36。数据范围当时我记得是 2 n 58这个上限很有意思58对应的最大乘积是 3 的18次方乘以 4算出来 1549681956还在32位int范围内。所以出题人给这个范围是有意控制结果不会溢出让你专心考算法不用在处理大数上纠结。1.2 为什么第一题选它稳中有变滴滴春招的第一题通常不是纯签到题会留一点门槛。划分这个题表面看很简单但实际能拉开差距的地方在于你是在背题还是真的理解了为什么要拆成3。如果你刷过力扣343那这道题对你来说就是送分题。但问题在于同样的题放在在线笔试环境里很多人会因为紧张把n2、n3这两个特判写反。我自己见过好几个同学思路完全正确却在边界上丢分——比如n2直接返回了2忘记题目要求至少拆成两个正整数。这种错误在本地随便测都不会犯但在笔试那种紧凑的节奏下就是容易犯所以我把它放在第一个坑里讲。1.3 先别急着写代码读题的三处关键第一处至少两个正整数。这意味着n2、n3不能直接返回本身必须拆分。第二处乘积最大。不是和最大不是数量最多而是连乘。这一点决定了我们要往数学方向想。第三处输出什么。题目要求输出最大乘积的值不是输出拆分成哪些数也不是输出方案数。所以只要算出一个数就行这让O(1)的数学解法成为可能。读题这件事往往比写代码更重要。尤其在线笔试题面不会太长但每个条件都是有意义的。把这三处关键点圈出来之后后面思路展开才不会跑偏。2. 从递归到动态规划没有数学直觉时怎么保底先说一句大实话如果你在笔试现场没有立刻想到拆成3完全不用慌。动态规划是比数学推导更通用的保底方案只要定义清楚状态暴力也能AC。2.1 最笨的枚举也是思路我当时拿到题第一时间想的不是最佳解而是我能不能枚举所有拆分方式对于n某个拆分的第一段可以是1、2、3……一直到n-1。如果第一段是j那么剩余部分是n-j。这时有两种选择不继续拆n-j那么当前乘积是 j * (n-j)继续拆n-j并且让n-j的内部达到最优那么当前乘积是 j * f[n-j]。这两种情况取最大值就是第一段拆成j时的最优结果。然后枚举所有j取全局最大就得到f[n]。这就是递归的想法写成公式就是f[n] max( j * (n-j), j * f[n-j] )其中 1 j n。不过直接递归会做大量重复计算比如f[10]依赖f[8]f[8]又依赖f[6]一层层重复下去指数级爆炸。所以要用记忆化或者直接改成自底向上的动态规划。2.2 状态定义与转移方程动态规划的状态定义非常直接dp[i] 表示正整数i拆分后能得到的最大乘积。初始化的时候dp[1]没意义因为1没法拆分成两个正整数所以直接从dp[2]开始算。转移方程dp[i] max( j * (i - j), j * dp[i - j] )枚举 j 从 1 到 i - 1。这里两个式子为什么要分别写打个比方你手里有一条绳子长度是i你想把它剪成若干段第一刀在j的位置剪下去。剪完之后左边那段固定不动右边那段有两种处理方式——要么不再剪直接作为一整段要么继续按最优方式剪下去。这两种情况都可能产生最大乘积所以都要考虑。2.3 手算一张表规律自己会跳出来我建议每个人都亲手算这张表算完你就明白为什么后面会有数学公式了。ndp[n]对应的一种最优拆分211132124422562369337123481833292733310363341154333212813333看到没有从7往后答案全部是2和3的乘积而且3占绝对主导。这张表不用背算一遍自然就信了。2.4 DP的时间复杂度与AC边界动态规划需要两层循环外层遍历i从2到n内层遍历j从1到i-1所以时间复杂度是O(n^2)空间复杂度O(n)。对于n58这个范围58的平方是3364计算量连零头都不到AC完全没压力。如果你在笔试现场没有找到数学规律直接写这个DP完全能拿到满分。这也是为什么我建议先把DP理解透——它是你的安全网。3. 数学推导为什么多拆3就是最优解如果你只满足于AC那DP就够了。但如果你想把这道题答得漂亮尤其是面试官让你证明一下的时候数学推导才是加分项。3.1 均值不等式的第一步拆成相等的数对于固定拆成k份的情况所有数之和是n要让乘积最大由均值不等式可以知道当这k个数都相等的时候乘积达到最大。也就是说最优拆分里每一份应该在某个固定值x附近总份数就是 n / x。所以问题变成了这个固定值x取多少乘积 x 的 (n/x) 次方最大我们对 x^(1/x) 这个函数做分析。对两边取对数就是 (ln x) / x求导之后是 (1 - ln x) / x^2。当x e时导数大于0当x e时导数小于0。也就是说x在e附近取到最大值e约等于2.718。离2.718最近的整数是3所以每一份尽量拆成3乘积才会最大。3.2 见到5以上的数先把它拆成3除了基于微积分的推导还有一个更简单的贪心证明面试时用这个反而更直观如果拆分结果里有一份是 x 5那么我们可以把它拆成 3 和 x - 3。拆完之后新的乘积是 3 * (x - 3)原来是 x。两者相减3(x - 3) - x 2x - 9。当 x 5 时2x - 9 1 或大于1也就是说拆完之后乘积一定会变大。反过来想任何大于等于5的因子都不应该出现在最优解里因为拆掉它只会更好。那么因子1呢如果最优解里出现了1说明这个1本来可以加到别的因数上。比如 1 和 3 合并成 4乘积从3变成41 和 2 合并成3乘积从2变成3。所以1也不可能出现在最优解里。枚举剩下的情况就很轻松了因子只能是2、3、4。而4本质上可以当成22乘积一样。于是最优解最终只和2、3有关。3.3 3个2不如2个3为什么2的数量最多只能有2个假设拆分结果里有三个2那么 222 6乘积是8。但如果我们把这三次拆分改成两个333 6乘积是9。9比8大说明三个2永远可以优化成两个3。因此最优解中2的个数不可能大于等于3只能是有0个、1个或2个。到这里结论已经完全收窄如果 n 能被3整除全拆成3。如果 n 除以3余1说明如果全拆3会多出一个1。1不能要那就从3的池子里借一个3出来134所以用4去替换3。公式变成 3^(q-1) * 4。如果 n 除以3余2直接乘一个2公式是 3^q * 2。3.4 别忘了n2和n3的特殊情况上面这套推导默认n比较大有得拆。但n2时2%32按公式算应该是 3^0 * 2 2可是2只有一个正整数不能拆所以正确答案是1。n3时3%30按公式算 3^1 3但3如果拆成12乘积才是2不拆就不是至少两个正整数所以正确答案是2。这就是为什么所有代码里都有个前置判断如果 n 3直接返回 n - 1。这个特判不是形式主义是真有无数人栽在这里。4. 三种语言实现Java、C、Python怎么写出稳定答案数学结论讲清楚之后代码其实就一句话的事。但真实笔试里不同语言有各自的坑我分别说。4.1 先说一个通用问题要不要用快速幂n 58 的时候直接用Java的Math.pow、C的pow或者Python的**都没问题。但我个人建议既然你已经明白了数学解不如顺手写一个快速幂几行代码既避免浮点误差又向面试官展示工程素养。下面给出的代码里我都用快速幂来算3的整数次幂这样即使未来题目把范围改成10000也不会出错。4.2 Java版本class Solution { public int integerBreak(int n) { if (n 3) { return n - 1; } int q n / 3; int r n % 3; if (r 0) { return pow3(q); } else if (r 1) { return pow3(q - 1) * 4; } else { return pow3(q) * 2; } } private int pow3(int k) { int result 1; int base 3; while (k 0) { if ((k 1) 1) { result * base; } base * base; k 1; } return result; } }Java这里要注意n/3得到的是整数除法余数用n%3。pow3(q - 1)在余数为1时q一定大于等于1因为n4时q1q-10不会变负数。4.3 C版本class Solution { public: int integerBreak(int n) { if (n 3) { return n - 1; } int q n / 3; int r n % 3; if (r 0) { return pow3(q); } else if (r 1) { return pow3(q - 1) * 4; } else { return pow3(q) * 2; } } private: int pow3(int k) { int result 1; int base 3; while (k 0) { if (k 1) { result * base; } base * base; k 1; } return result; } };C唯一需要提防的是如果你直接用pow(3, q)它返回的是double。在n58时double转int还好但如果你某天把n范围调大double的精度会逐渐不够乘出来的结果会差一两个数。用自写的整型快速幂就没有这个烦恼。4.4 Python版本class Solution: def integerBreak(self, n: int) - int: if n 3: return n - 1 q, r divmod(n, 3) if r 0: return 3 ** q if r 1: return 3 ** (q - 1) * 4 return 3 ** q * 2Python有自己的大整数**是任意精度的所以这段代码看起来最干净。在线笔试时用Python写这种题最舒服甚至不用自己写快速幂3 ** q也不会溢出。不过要注意divmod(n, 3)返回商和余数用起来比两个运算符稍微整齐一点但两者都可以。4.5 动态规划兜底模板万一你在笔试现场就是死活想不起来数学结论直接用动态规划。我给一份Java的DP兜底代码逻辑清晰15行以内class Solution { public int integerBreak(int n) { int[] dp new int[n 1]; dp[2] 1; for (int i 3; i n; i) { for (int j 1; j i; j) { dp[i] Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j])); } } return dp[n]; } }C和Python写法几乎一样就是把Math.max换成max即可。如果只求AC这个方案完全够用而且不需要证明。我也建议你在平时练习时把DP版本和数学版本都写一遍面试被追问的时候才能讲出完整的思维过程。5. 在线测试与我在本地/在线OJ踩过的坑5.1 怎么快速验证代码这道题在力扣的原题是整数拆分题号343直接搜就能找到。在线笔试前我强烈建议把这种基础题目至少刷三遍第一遍背思路第二遍不看题解默写第三遍把三种语言都过一遍。我自己的经验是第三遍通常能暴露出很多自以为会了但实际写不出来的细节。如果不想依赖在线OJ也可以在本地写一个简单的main函数把n从2到58全跑一遍输出每个结果然后对照上文的表检查。只要2到12的结果都对后面基本不会错。5.2 坑一n2和n3返回了本身这是最高频的错误。数学公式算出来的结果对n2和n3恰好等于n本身但题目要求至少拆成两个正整数所以必须特判。上个月我帮一个朋友改代码他整段逻辑全对唯独把特判写在后面导致n3直接走数学分支返回3白丢分。5.3 坑二余数为1时忘记把3的个数减一n10时10除以3商3余1。如果你写成3^3 * 1得到27但正确答案是3^2 * 4 36。为什么因为多出来的余数1不能单独存在必须从已有的3里借一个出来变成4。4虽然只比3大1但在乘积里从3变成4效果很不一样。更极端的例子是n44除以3商1余1如果按3^1 * 1算结果是3而正确结果是4。特判虽然能拦住n4但拦不住n7、10、13这些数所以公式必须写对。5.4 坑三用Math.pow然后强转int精度跌跌撞撞Java和C的pow返回的是浮点数。n58时pow(3, 18)在double里还能精确表示乘4转int也没问题。但如果你把这道题扩展成取模版本n给到1e9再调用pow就会出现指数级误差。所以我在上面特意写了整型快速幂这是更稳妥的做法。5.5 坑四Python很舒服但C要用long longn58时int够用可万一你用动态规划版本算更大的数比如n100乘积已经超过int范围了。C里如果dp数组是int直接溢出。所以写DP时C建议用vectorlong longJava用long[]Python无所谓。5.6 如果题目改成取模版本怎么办春招题有时会加一句答案对1000000007取模这时数学解法仍然成立但快速幂需要升级为取模快速幂。每次乘法之后取模循环逻辑不变。如果n特别大n/3和n%3本身不会溢出但乘方过程要小心。这种变形在后续面试中很容易被问到建议你自己推一遍。我在实际笔试中用这道题最多的体会是它看起来是一道数学题但真正的分水岭在边界处理和三语言基本功上。会背公式的人很多能在压力下写出无bug代码的人才是面试官想要的。所以别只盯着结论是拆成3把每一行代码、每一个特判都吃透这道题才算真正学会了。

整数拆分问题全解：动态规划、数学优化与三语言实现

相关推荐

HuggingFace英译中模型迁移ONNX：CPU推理加速与INT8量化实战

Caffeine+Redis两级缓存：高并发下的热key与穿透治理实战

Mesh组网实战：告别单路由死角，全屋Wi-Fi无缝漫游

更多资讯

Tiki-taka算法光伏模型参数辨识：Matlab实现与实战

AI 辅助嵌入式代码生成实战：驱动与 RTOS 任务从提示词到落地

Java Swing实现简单画图工具

从公共基础设施到资本增值工具：平台异化下内容生态的崩塌与独立站点出路

AI 辅助嵌入式系统设计：接口定义与模块划分的正确打开方式

如何让代码与流程无可挑剔：轻量级自动化检查实践

今日更新

PHP htmlentities()函数用法讲解

AI Agent工程实战：从七要素到七个决策点的系统设计指南

AI入局芯片设计验证：验证收敛50倍加速的真相与应对

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？