教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文以「算法通关手册」AlgoNote 仓库中 0343. 整数拆分 的官方题解为主体系统讲解这道中等难度动态规划题的完整推导过程从问题建模、状态定义到状态转移方程与代码实现。该题同时被仓库收录于「无串线性 DP」专题是学习线性动态规划最典型的入门题目之一。读完本文你将掌握整数拆分求最大乘积这一经典 DP 模型的五步解题套路并能直接复现可运行代码。一、题目概览题目链接0343. 整数拆分 - 力扣在 AlgoNote 的分类体系中该题位于 0300-0399 题解目录标签为数学、动态规划难度为中等。在 00_06_categories_list.md 中它被收录进「无串线性 DP 问题」专题列表与「两个键的键盘」「丑数 II」「完全平方数」等经典题并列。题目描述给定一个正整数 $n$将其拆分为 $k (k \ge 2)$ 个正整数的和并使这些整数的乘积最大化。要求返回可以获得的最大乘积。关键约束$2 \le n \le 58$。由于 $n$ 最大仅为 58乘积结果完全在 32 位整数范围内无需考虑大数溢出问题。示例示例 1输入: n 2 输出: 1 解释: 2 1 1, 1 × 1 1。示例 2输入: n 10 输出: 36 解释: 10 3 3 4, 3 × 3 × 4 36。注意题目对拆分方式的隐含要求必须拆成至少 2 个正整数$k \ge 2$因此 $n 2$ 时只能拆成 $1 1$最大乘积为 1而不是不拆分得到的 2。二、为什么这道题适合用动态规划在深入推导前先对照仓库中 08_01_dynamic_programming_basic.md 总结的动态规划三大特征来检验本题最优子结构整数 $i$ 拆分的最大乘积可以由更小整数 $i - j$ 拆分的最大乘积递推得到——整体最优解包含子问题最优解。重叠子问题在枚举第一个拆分项 $j$ 的过程中同一个较小的数如 $dp[i-j]$会被反复计算天然存在大量重叠子问题。无后效性一旦 $dp[i]$ 确定后续阶段不再修改它只依赖前面已经算好的阶段值。三个特征全部满足这正是教科书级的一维线性 DP 模型。在仓库的 08_05_linear_dp_03.md 中本题被选作「无串线性 DP 问题经典例题」第 4.1 节紧接其后的是同类经典题「0650. 只有两个键的键盘」两者共享按正整数递推、枚举拆分/因子的解题框架适合对照学习。三、动态规划五步法完整推导本仓库的题解遵循标准的 DP 五步法阶段划分 → 定义状态 → 状态转移 → 初始条件 → 最终结果。下面逐步拆解。3.1 阶段划分按照正整数进行划分。从小到大依次求解 $i 0, 1, 2, \dots, n$ 每个整数对应的问题前一个阶段求解完成后才进入后一个阶段。3.2 定义状态定义状态 $dp[i]$ 表示将正整数 $i$ 拆分为至少 2 个正整数的和之后这些正整数的最大乘积。这里的状态定义是整个解法的核心$dp[i]$ 描述的是拆分后的最大乘积它天然隐含了必须拆分这一约束从而在递推中自动满足题目 $k \ge 2$ 的要求。3.3 状态转移方程当 $i \ge 2$ 时假设正整数 $i$ 拆分出的第 1 个正整数是 $j(1 \le j i)$则剩余部分为 $i - j$此时有两种策略不再继续拆分将 $i$ 拆分为 $j$ 和 $i - j$ 的和$i - j$ 不再拆分乘积为 $j \times (i - j)$继续递归拆分将 $i$ 拆分为 $j$ 和 $i - j$ 的和且 $i - j$ 继续拆分为多个正整数此时乘积为 $j \times dp[i - j]$直接复用子问题最优解。$dp[i]$ 取两者中的最大值。由于 $1 \le j i$需要遍历所有可能的 $j$因此完整的转移方程为$$ dp[i] \max_{1 \le j i}\lbrace \max(j \times (i - j),\ j \times dp[i - j]) \rbrace $$直观理解枚举第一个拆出来的数 $j$ 的所有可能取值对每个 $j$ 比较剩下不再拆与剩下继续拆两种方案的乘积取全局最大值。$dp[i - j]$ 的复用正是动态规划避免重复计算的关键。3.4 初始条件$dp[0] 0$、$dp[1] 0$$0$ 和 $1$ 都不能被拆分为至少两个正整数无法产生有效拆分故其最大乘积记为 0。3.5 最终结果根据状态定义将正整数 $n$ 拆分为至少 2 个正整数之和后得到的最大乘积即为 $dp[n]$直接返回该值。四、代码实现可运行class Solution: def integerBreak(self, n: int) - int: dp [0 for _ in range(n 1)] for i in range(2, n 1): for j in range(i): dp[i] max(dp[i], (i - j) * j, dp[i - j] * j) return dp[n]代码要点注释dp [0 for _ in range(n 1)]初始化长度为 $n 1$ 的一维表格下标 01 自动满足初始条件 $dp[0] dp[1] 0$外层循环for i in range(2, n 1)按阶段从小到大递推每个整数内层循环for j in range(i)枚举第 1 个拆分项 $j$覆盖 $1 \le j i$ 的全部取值$j 0$ 时(i - j) * j 0、dp[i - j] * j 0不影响取最大值的结果可看作无害的边界遍历max(dp[i], (i - j) * j, dp[i - j] * j)一行同时比较三种情况——当前已记录的最优值、不再拆分方案、继续拆分方案实现状态转移方程。该实现与仓库 08_05_linear_dp_03.md 第 4.1 节中的代码完全一致可直接复制到力扣对应题目中运行。五、复杂度分析时间复杂度$O(n^2)$。外层循环遍历 $n$ 个阶段$O(n)$内层对每个 $i$ 枚举 $j$合计约 $O(n^2)$ 次比较总体为平方级空间复杂度$O(n)$。仅使用长度为 $n 1$ 的一维数组保存状态。结合题目约束 $2 \le n \le 58$$O(n^2)$ 的时间开销对最大规模也完全可接受这正是题目刻意控制 $n$ 上限的原因。六、从仓库结构看本题的定位与延伸6.1 仓库中的多重收录本题在 AlgoNote 仓库中出现于多处形成题解 专题 分类的完整学习闭环位置作用题解文档本题的独立完整题解即本文主体08_05_linear_dp_03.md「无串线性 DP」章节的经典例题4.1 节08_14_counting_dp.md计数 DP 章节 2.2 节亦收录了本题的完整推导00_06_categories_list.md分类刷题列表「无串线性 DP 问题」表格这种专题讲解 分类索引的双重结构体现了仓库按专题分类刷题的编排思路见 00_04_leetcode_guide.md 3.3.3 节。6.2 同类题目延伸练习掌握本题的按正整数递推 枚举拆分/因子框架后可顺藤摸瓜练习仓库中的以下相关题目0650. 只有两个键的键盘同属无串线性 DP但改为枚举因子、求最小操作次数是本题最大化乘积的对偶问题对比练习可加深对状态设计的理解0279. 完全平方数同样在一维 DP 中枚举拆分项完全平方数感受不同枚举维度对转移方程的影响0264. 丑数 II同一专题列表中的进阶题可检验对 DP 递推顺序的掌握程度。6.3 从数学标签看另一种视角题目标签同时包含数学说明除了 DP 还有数学规律解法直观上为使乘积最大应尽量少拆出 1并优先拆分出 3当 $n$ 足够大时$3 \times (n - 3) \ge n$且 3 比 2 更划算。不过仓库题解以动态规划作为主要讲解方案因其通用性更强——数学规律依赖具体数值特性而 DP 五步法可迁移到大量同类问题上这也是本题被选作线性 DP 经典例题的原因。七、小结通过「整数拆分」这道题我们可以完整走一遍动态规划的标准流程划分子问题阶段 → 定义拆分后最大乘积的状态 → 枚举首个拆分项并比较拆/不拆两条转移路径 → 初始化不可拆的边界 → 递推得到 $dp[n]$。这五个步骤在 AlgoNote 仓库中均有完整文字与代码佐证且该模型可以直接复用到完全平方数、丑数、两个键的键盘等一维线性 DP 题目中。建议结合 08_01_dynamic_programming_basic.md 先理解最优子结构、重叠子问题与无后效性三大特征再回到本题反复推演即可把会做一题升级为掌握一类。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐丑数 IILeetCode 0264动态规划 三指针解法精讲AlgoNote 算法通关手册题解丑数 IILeetCode 0264动态规划 三指针解法精讲AlgoNote 算法通关手册题解 本篇技术指南围绕 LeetCode 0264「丑数 I教程文档知识库AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划AlgoNote「算法通关手册」题解精讲LeetCode 0091 解码方法字符串 动态规划 导读 本篇是 AlgoNote算法通关手册中 009教程文档知识库AlgoNote 算法题解精讲LeetCode 0139「单词拆分」动态规划解法AlgoNote 算法题解精讲LeetCode 0139「单词拆分」动态规划解法 本文基于 AlgoNote 算法通关手册仓库中的 word break.md教程文档知识库上一篇2025黑苹果完整指南从零开始打造稳定macOS系统的终极方案下一篇如何通过EverythingToolbar实现Windows任务栏闪电级文件搜索创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
