企业官网建设流程全解析

• 文档
• 教程
• 知识库

本篇题解以 leetcode 仓库中 problems/343.integer-break.md 为骨架，完整还原一道经典"换皮"题的思考全过程：先对问题做数学抽象，再按"递归 → 记忆化递归 → 自底向上动态规划"的路径逐步优化，并对照仓库 thinkings/dynamic-programming.md 中的重叠子问题、最优子结构、状态定义等理论，讲清每一步"为什么能这么想、为什么能这么改"。读完你将掌握一套可复用的动态规划解题心法，并能识别出与本题同源的换皮题目。

题目描述

给定一个正整数n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1：

输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2：

输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明：你可以假设n不小于 2 且不大于 58。在仓库的题解清单中，本题被收录于中等难度列表，见 collections/medium.md。

前置知识与考察公司

前置知识：递归、动态规划。

常见考察公司：阿里、腾讯、百度、字节。

本题要求"至少拆成两段"，这一限定是理解后续所有转移方程的关键，也是最容易被忽略的细节之一。

解题思路：什么才是好的题解

很多题解只有两句话就贴上代码，例如：

class Solution: def integerBreak(self, n: int) -> int: dp = [1] * (n + 1) for i in range(3, n + 1): for j in range(1, i): dp[i] = max(j * dp[i - j], j * (i - j), dp[i]) return dp[n]

这种题解只对"自己已经会做、只是去题解区找新解法"的人有效。而大多数看题解的人是自己没思路、不会做的人，对他们来说，这种直接给出答案的写法毫无帮助，甚至会产生"我已经会了"的假象。

好的题解应当新手友好，并且完整展现解题人的思考过程：看到题目先想到了什么（对错没有关系），头脑中如何一步步筛选出最终算法，最终解法是"如何想到的"，有没有先行知识作为铺垫。

下面完整还原这道题的思考链路。

第一步：抽象问题，识别本质

看到题目，先对问题做抽象。这种抽象能力是必须的——LeetCode 上有很多"穿着华丽外表的题"，扒开外壳后会发现本质大同小异，甚至完全相同。

本题就是一个典型：它与剑指 Offer 的原题《剪绳子》本质一模一样，只是换了描述方式。仓库的字节跳动算法面试题清单 selected/byte-dance-algo-ex.md 中同样指出：《割绳子》实际上就是 343. 整数拆分的"换皮题"；selected/mother-01.md 也将本题作为"扒一扒这种题的外套"的代表案例。类似的换皮例子还有力扣 137 与 645（"只出现一次的数字"系列），大家可以自行归纳总结。

培养自己抽象问题的能力，不管是在算法上还是工程上，务必记住这句话。

回到本题，抽象一下就是：

• 令f(n)表示：将n拆分为至少两个正整数的和，所能得到的最大乘积；
• 求：f(n)的值。

注：本题实际上也可以从纯数学角度求解（例如通过均值不等式推导出"尽量拆成 3"的结论），但大多数人并不想看重数学推导，即使看了，感受多半是"好 nb，然而并没有什么用"。因此这里采用更通用的递归 / 动态规划视角。

第二步：第一直觉——递归

经过抽象，第一直觉是这可能是一道数学题。但假设没有数学加持，下一步自然会想：是否可以把所有拆分情况枚举出来，再求最大值。问题于是转化为"如何枚举所有情况"。

经过几秒钟思考，会发现这是一个很明显的递归问题，具体推理过程如下：

• 将原问题抽象为f(n)；
• 那么f(n)等价于max(1 * f(n-1), 2 * f(n-2), ..., (n-1) * f(1), i * (n-i))。

其中i * (n-i)这一项最容易忽略，它表示的是"恰好分成两段"的情况。之所以必须显式包含它，是因为f的定义是"至少分成两段"（题目限制），而f(k)本身（k < n 时）不会覆盖"恰好拆成i和n-i两段"这个不继续拆分的情形。

用数学公式表达就是：

f(n) = max( 1*f(n-1), 2*f(n-2), ..., (n-1)*f(1), i*(n-i) )

直接把这个公式翻译成代码：

class Solution: def integerBreak(self, n: int) -> int: if n == 2: return 1 res = 0 for i in range(1, n): res = max(res, max(i * self.integerBreak(n - i), i * (n - i))) return res

毫无疑问，超时了。原因很简单：算法中包含大量重复计算——integerBreak(n-i)会在不同的分支里被反复求解。这与仓库 thinkings/dynamic-programming.md 中"重叠子问题"的描述完全一致：递归树中同一个子问题被多次计算，例如f(n-2)与f(n-3)都会被重复求解多次，实际上计算一次就够了。

提示：大家可以自己画一棵递归树，直观感受一下重复计算的规模——最坏情况下是指数级的。

看到这里，有没有一种"殊途同归"的感觉？递归是自上而下的思考方式，符合人类的直觉；而它暴露出的重叠子问题，正是后续所有优化的切入点。

第三步：考虑优化——记忆化递归

既然瓶颈是重复计算，那么很自然的方案是：用一个 hashtable 缓存已经计算过的值，下次遇到相同参数时直接返回，即"记忆化递归"。

仓库 thinkings/dynamic-programming.md 对记忆化给出了清晰的解释：之所以可以缓存，是因为这里的递归函数是数学意义上的函数——参数确定，返回值就确定，不依赖也不改变外部变量。因此用memo（key 为参数，value 为返回值）缓存后，重复子问题只需计算一次，节省的时间等价于重叠子问题的个数。

代码实现如下（为了简洁，直接使用lru_cache注解，同样可以 AC）：

class Solution: @lru_cache() def integerBreak(self, n: int) -> int: if n == 2: return 1 res = 0 for i in range(1, n): res = max(res, max(i * self.integerBreak(n - i), i * (n - i))) return res

记忆化递归的时间复杂度降为 O(n²)（每个状态计算一次，每次需要枚举 O(n) 个拆分点），空间复杂度 O(n)。

第四步：动态规划——自底向上

看到这里的同学应该已经发现了：下一步就是将其改造为动态规划。递归是自上而下（top-down）的思考方式，这符合人们思考问题的习惯；而将其反转成自底向上（bottom-up）的方式，就是动态规划。

现在再回头看文章开头的代码，一切都变得顺理成章：

class Solution: def integerBreak(self, n: int) -> int: dp = [1] * (n + 1) for i in range(3, n + 1): for j in range(1, i): dp[i] = max(j * dp[i - j], j * (i - j), dp[i]) return dp[n]

推演过程如下：

1. dp table 存储的是什么：dp table 存储的是f(n)的值。一个自然的想法是令dp[i]等价于f(i)；又因为原问题等价于f(n)，所以原问题的答案也等价于dp[n]。

2. 转移方程从递归公式平移而来：dp[i]等价于f(i)，那么上面针对f写出的递归公式对dp同样适用。把关键语句：

   res = max(res, max(i * self.integerBreak(n - i), i * (n - i)))

   翻译成 dp 的语言就是：

   dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j)))

3. 这里的 n 到底是什么：dp 是自底向上的思考方式，在计算到n之前是看不到整体的n的。因此这里的n实际上是1, 2, 3, ..., n的递推序列。自然用一层循环来生成这一系列 n 值。

4. 内层循环的边界：还要生成一系列j值，注意到n - j必须大于 0，因此j只需循环到i - 1即可。

5. 为什么从 3 开始：dp[2]的答案已知为 1（2 = 1 + 1），且j * dp[i - j]中当i - j < 2时没有意义，因此外层循环从 3 起步。

这样，代码就"不难得出"了。

复杂度分析：动态规划解法时间复杂度 O(n²)（两层循环，约 n²/2 次比较），空间复杂度 O(n)（仅一个长度为 n+1 的数组）。对于n ≤ 58的题目范围完全足够。

正确性依据：该解法成立依赖动态规划的两个前提条件（详见 thinkings/dynamic-programming.md）：

• 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质。本题中，f(n)的最优解由某个f(n-j)与j组合而成，子问题互不影响，满足最优子结构；
• 无后效性：子问题的解一旦确定就不再改变，不受之后更大问题的求解决策影响。本题dp[i]一旦算定，后续dp[k]（k > i）只会读取它而不会修改它，满足无后效性；
• 同时它天然消除了重叠子问题的重复计算——每个dp[i]只被计算一次。

关键点

• 数学抽象：把题目文字翻译成函数f(n)，看清"至少两段"的边界约束；
• 递归分析：从f(n) = max(1*f(n-1), ..., (n-1)*f(1), i*(n-i))出发枚举所有拆分；
• 记忆化递归：用 hashtable /lru_cache消除重叠子问题的重复计算；
• 动态规划：把自上而下的递归反转成自底向上的 dp 填表，转移方程与递归公式一一对应。

总结

培养自己的解题思维很重要：不要直接看别人的答案，而是要把别人的东西变成自己的。要做到这一点，就要追问三个问题——"他们是怎么想到的"、"想到这点是不是有什么前置知识"、"类似题目有哪些"。

最优解通常不是一下子想到的，这需要你在不那么优的解上摔很多次跟头之后才能记住。因此在没有掌握之前，不要直接去看最优解；掌握之后，不仅要会写最优解，还鼓励一题多解，从多个角度思考问题。

这条"递归 → 记忆化递归 → 动态规划"的演进路线，在仓库 thinkings/dynamic-programming.md 中有系统性的理论讲解：从记忆化递归（查表的递归）讲起，再到动态规划的最优子结构、无后效性、状态定义三要素，最后落到各种题型套路。建议将本题与那篇理论文章对照阅读，把"重叠子问题"的递归树画出来，亲手感受记忆化带来的收益，然后再尝试把同样的思路迁移到其他题目上。

扩展

正如开头所说，这种"换皮"套路实在太常见了。本题的变体包括但不限于：

• 剑指 Offer《剪绳子》及其 II 版本（涉及大数取模）；
• 其他"将问题抽象为函数、用记忆化/DP 消除重叠子问题"的同源题目。

希望读者能学会识别问题的本质，而不是死记某一题的答案。将本题收录进自己的解题模板库之后，再遇到任何"拆分 + 乘积/和最大化"类的题目，都可以第一时间联想到这套解法框架，从数学抽象出发，先写递归，再谈优化，最后落成动态规划。

• 文档
• 教程
• 知识库