文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载本篇题解以 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 对记忆化给出了清晰的解释之所以可以缓存是因为这里的递归函数是数学意义上的函数——参数确定返回值就确定不依赖也不改变外部变量。因此用memokey 为参数value 为返回值缓存后重复子问题只需计算一次节省的时间等价于重叠子问题的个数。代码实现如下为了简洁直接使用lru_cache注解同样可以 ACclass 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]推演过程如下dp table 存储的是什么dp table 存储的是f(n)的值。一个自然的想法是令dp[i]等价于f(i)又因为原问题等价于f(n)所以原问题的答案也等价于dp[n]。转移方程从递归公式平移而来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)))这里的 n 到底是什么dp 是自底向上的思考方式在计算到n之前是看不到整体的n的。因此这里的n实际上是1, 2, 3, ..., n的递推序列。自然用一层循环来生成这一系列 n 值。内层循环的边界还要生成一系列j值注意到n - j必须大于 0因此j只需循环到i - 1即可。为什么从 3 开始dp[2]的答案已知为 12 1 1且j * dp[i - j]中当i - j 2时没有意义因此外层循环从 3 起步。这样代码就不难得出了。复杂度分析动态规划解法时间复杂度 O(n²)两层循环约 n²/2 次比较空间复杂度 O(n)仅一个长度为 n1 的数组。对于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 消除重叠子问题的同源题目。希望读者能学会识别问题的本质而不是死记某一题的答案。将本题收录进自己的解题模板库之后再遇到任何拆分 乘积/和最大化类的题目都可以第一时间联想到这套解法框架从数学抽象出发先写递归再谈优化最后落成动态规划。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐LeetCode 343 Integer Break 整数拆分全解从暴力递归到数学最优解的七种思路LeetCode 343 Integer Break 整数拆分全解从暴力递归到数学最优解的七种思路 本文基于本仓库 articles/integer brea示例工程教程LeetCode 139. 单词拆分Word Break题解从暴力匹配到记忆化递归与动态规划LeetCode 139. 单词拆分Word Break题解从暴力匹配到记忆化递归与动态规划 导读 本文基于 leetcode 题解仓库中的 139. 单文档教程知识库LeetCode 1043 题解用记忆化递归与动态规划求分隔数组的最大和LeetCode 1043 题解用记忆化递归与动态规划求分隔数组的最大和 本篇基于仓库中的题解文档 1043. 分隔数组以得到最大和 https://link文档教程知识库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考