LeetCode-Book 整数拆分343最优解从均值不等式到贪心拆 3 的数学推导与多语言实现【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文以 LeetCode-Book 仓库中《343. 整数拆分》文档为主体完整推导将正整数 n 拆分为若干正整数之和并使乘积最大的数学原理先用算术几何均值不等式证明拆分数字相等时乘积最大再通过求导与数值对比锁定最优拆分因子为 3最终给出 O(1) 的贪心算法流程并对照仓库中的 Python / Java / C 源码给出可直接运行的实现与边界条件分析。一、问题定义与建模题目LeetCode 343. Integer Break / 剑指 Offer 14-I 剪绳子给定一个正整数n将其拆分为至少两个正整数的和求这些拆分数字乘积的最大值。仓库文档将原题表述为如下等价形式设将整数 $n$ 拆分为 $a$ 个小数字$a \geq 2$$$ n n_1 n_2 \cdots n_a $$本题等价于求解$$ \max(n_1 \times n_2 \times \cdots \times n_a) $$该问题的难点在于拆分数量 $a$ 与每个拆分数字 $n_i$ 都是变量直接枚举代价过高。而《343. 整数拆分》文档给出了一个优雅的数学路线——先固定 $a$ 讨论怎么分再对 $a$等价于对公共因子 $x$讨论分多大两步即可锁定全局最优结构。二、数学推导为什么最优拆分与均分有关2.1 第一步拆分数量确定时均分乘积最大文档首先引入算术几何均值不等式AM-GM Inequality$$ \frac{n_1 n_2 \cdots n_a}{a} \geq \sqrt[a]{n_1 n_2 \cdots n_a} $$等号当且仅当 $n_1 n_2 \cdots n_a$ 时成立。推论一若拆分的数量 $a$ 确定则各拆分数字相等时乘积最大。也就是说讨论拆成多少个之前可以先假定每个拆分数字都等于同一个因子 $x$。2.2 第二步转化为单变量极值问题设将数字以因子 $x$ 等分为 $a$ 个即 $n ax$则乘积为 $x^a$。由于 $n$ 是常数可以做如下恒等变形$$ x^a x^{\frac{n}{x}} \left(x^{\frac{1}{x}}\right)^n $$因为 $n$ 固定所以当 $x^{\frac{1}{x}}$ 取最大值时乘积达到最大值。问题被转化为求函数 $y x^{\frac{1}{x}}$ 的极大值。2.3 对 x 求导找到极值点文档给出了完整求导过程先取对数再对 $x$ 求导$$ \begin{aligned} \ln y \frac{1}{x} \ln x \text{取对数} \ \frac{1}{y} \dot{y} \frac{1}{x^2} - \frac{1}{x^2} \ln x \frac{1 - \ln x}{x^2} \text{对 $x$ 求导} \ \dot{y} \frac{1 - \ln x}{x^2} x^{\frac{1}{x}} \text{整理得} \end{aligned} $$令 $\dot{y} 0$则 $1 - \ln x 0$易得驻点为$$ x_0 e \approx 2.7 $$根据导数的符号变化可知 $x_0$ 为极大值点$$ \dot{y}\begin{cases} 0 , x \in (-\infty, e) \ 0 , x \in (e, \infty] \end{cases} $$2.4 因子必须是整数在 2 和 3 之间比较由于拆分因子 $x$ 必须为整数最接近 $e$ 的整数是 $2$ 或 $3$。分别代入$$ y(3) 3^{1/3} \approx 1.44 \ y(2) 2^{1/2} \approx 1.41 $$文档还给出一个口算对比方法给两数字同时取 $6$ 次方再对比整数大小——$$ [y(3)]^6 (3^{1/3})^6 9 \ [y(2)]^6 (2^{1/2})^6 8 $$因为 $9 8$所以 $y(3) y(2)$即 $x 3$ 时乘积最大。推论二将数字 $n$ 尽可能以因子 $3$ 等分时乘积最大。三、拆分规则与算法流程3.1 三条拆分规则由推论二可以直接归纳出贪心拆分的三条规则文档原文最优3。把数字 $n$ 尽可能拆为多个因子 $3$余数可能为 $0, 1, 2$ 三种情况。次优2。若余数为 $2$则保留不再拆为 $1 1$因为 $1 \times 1 2$。最差1。若余数为 $1$则应把一份 $3 1$ 替换为 $2 2$因为 $2 \times 2 3 \times 1$。3.2 算法流程文档给出了 O(1) 的分情况讨论流程当 $n \leq 3$ 时按照规则本应不拆分但题目要求必须拆成至少两个正整数因此必须拆出一个因子 $1$即返回 $n - 1$。当 $n 3$ 时求 $n$ 除以 $3$ 的整数部分 $a$ 和余数部分 $b$即 $n 3a b$分为三种情况当 $b 0$ 时直接返回 $3^a$当 $b 1$ 时要将一个 $1 3$ 转换为 $2 2$因此返回 $3^{a-1} \times 4$当 $b 2$ 时返回 $3^a \times 2$。边界验证$n 2, 3$ 时返回 $n - 1$$n 2$唯一拆分 $1 1$乘积 $1$恰好等于 $2 - 1$$n 3$拆分 $1 2$乘积 $2$恰好等于 $3 - 1$若拆成 $111$ 乘积只有 $1$。对于 $n 3$ 的常规情况例如 $n 10$$a 3, b 1$答案为 $3^{2} \times 4 36$对应的拆分为 $3 3 2 2$。该用例在仓库的驱动代码中已给出见下文。3.3 复杂度分析文档给出的复杂度结论时间复杂度 $O(1)$仅有求整、求余、次方运算。空间复杂度 $O(1)$a和b使用常数大小额外空间。需要说明的是求整、求余、幂运算为 $O(1)$ 的前提是数字在机器数范围内如 32/64 位整数此时 CPU 一条指令即可完成若涉及任意精度大整数则需按位运算重新考量。文档亦通过外部资料佐证了该结论不超过机器数的整数取模可视为 $O(1)$浮点取幂Math.pow底层 C 库实现同样可视为 $O(1)$。四、多语言实现仓库源码对照4.1 Python 实现仓库中的 lc_343_integer_break.py 与文档代码完全一致from include import * # Solution Code class Solution: def integerBreak(self, n: int) - int: if n 3: return n - 1 a, b n // 3, n % 3 if b 0: return int(math.pow(3, a)) if b 1: return int(math.pow(3, a - 1) * 4) return int(math.pow(3, a) * 2)关于幂运算的选择文档特别强调Python 中常见有三种幂计算函数——**幂运算符和pow()的时间复杂度均为 $O(\log a)$math.pow()始终调用 C 库的pow()函数执行浮点取幂时间复杂度为 $O(1)$。因此本题为了达到严格的 $O(1)$ 时间应使用math.pow(3, a)而非3 ** a或pow(3, a)。4.2 Java 实现仓库中的 lc_343_integer_break.java 与文档代码一致package lc_343_integer_break; import include.*; import java.util.*; // Solution Code class Solution { public int integerBreak(int n) { if(n 3) return n - 1; int a n / 3, b n % 3; if(b 0) return (int)Math.pow(3, a); if(b 1) return (int)Math.pow(3, a - 1) * 4; return (int)Math.pow(3, a) * 2; } }Java 的Math.pow(3, a)底层调用 C 库浮点取幂同样满足 $O(1)$随后用(int)强转回整数返回。4.3 仓库中同源题目的扩展剪绳子系列该解法并非孤例在仓库的《剑指 Offer》目录中可找到同源题目与变体可以交叉印证算法正确性剑指 Offer 14-I 剪绳子Python、Java、C与本题逻辑完全相同其中 C 版本使用pow(3, a)与int返回测试用例n 10输出36#include ../include/include.hpp class Solution { public: int cuttingRope(int n) { if (n 3) return n - 1; int a n / 3, b n % 3; if (b 0) return pow(3, a); if (b 1) return pow(3, a - 1) * 4; return pow(3, a) * 2; } };剑指 Offer 14-II 剪绳子 IIPython 大数版当 $n$ 极大时$3^a$ 会溢出机器数。Python 因语言特性可天然处理大整数只需对结果取模 $1000000007$class Solution: def cuttingRope(self, n: int) - int: if n 3: return n - 1 a, b, p n // 3, n % 3, 1000000007 if b 0: return 3**a % p if b 1: return 3 ** (a - 1) * 4 % p return 3**a * 2 % p注意此处a很大使用3 ** a整型幂运算$O(\log a)$而非math.pow浮点会丢精度可见两种幂函数在不同场景下各有用途。五、解法对比与总结5.1 为什么贪心拆 3 优于 DP本题在 LeetCode 官方题解中属于动态规划分类dp[i] max(j * (i - j), j * dp[i - j])复杂度 $O(n^2)$而本文基于数学推导的贪心解法只需要常数次求整、求余、取幂复杂度为 $O(1)$。从源码结构看仓库为本题提供了单一的最优数学解法文件Python 与 Java 各一份而在其他多解法题目中仓库会以_s1、_s2后缀保留多个实现这从侧面印证了拆 3 分情况讨论是该题最推荐的方案。5.2 算法要点速记情形返回值对应拆分$n \leq 3$$n - 1$必须拆分拆出因子 $1$$n 3,\ b 0$$3^a$$3 3 \cdots 3$$n 3,\ b 1$$3^{a-1} \times 4$$3 \cdots 3 2 2$合并 $31$$n 3,\ b 2$$3^a \times 2$$3 \cdots 3 2$5.3 一句话总结本题的完整推理链为均值不等式 → 均分最优 → 求 $x^{1/x}$ 极值 → 驻点 $e$ → 整数因子取 $3$ → 按余数 $0/1/2$ 分情况讨论。这套先证明结构、再贪心落码的思路不仅让integerBreak能以 O(1) 时间求解也直接迁移到剪绳子 I/II 等变体题目中是笔试面试中数学贪心类问题的经典范式。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 整数拆分（343）最优解：从均值不等式到贪心拆 3 的数学推导与多语言实现
LeetCode-Book 整数拆分343最优解从均值不等式到贪心拆 3 的数学推导与多语言实现【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文以 LeetCode-Book 仓库中《343. 整数拆分》文档为主体完整推导将正整数 n 拆分为若干正整数之和并使乘积最大的数学原理先用算术几何均值不等式证明拆分数字相等时乘积最大再通过求导与数值对比锁定最优拆分因子为 3最终给出 O(1) 的贪心算法流程并对照仓库中的 Python / Java / C 源码给出可直接运行的实现与边界条件分析。一、问题定义与建模题目LeetCode 343. Integer Break / 剑指 Offer 14-I 剪绳子给定一个正整数n将其拆分为至少两个正整数的和求这些拆分数字乘积的最大值。仓库文档将原题表述为如下等价形式设将整数 $n$ 拆分为 $a$ 个小数字$a \geq 2$$$ n n_1 n_2 \cdots n_a $$本题等价于求解$$ \max(n_1 \times n_2 \times \cdots \times n_a) $$该问题的难点在于拆分数量 $a$ 与每个拆分数字 $n_i$ 都是变量直接枚举代价过高。而《343. 整数拆分》文档给出了一个优雅的数学路线——先固定 $a$ 讨论怎么分再对 $a$等价于对公共因子 $x$讨论分多大两步即可锁定全局最优结构。二、数学推导为什么最优拆分与均分有关2.1 第一步拆分数量确定时均分乘积最大文档首先引入算术几何均值不等式AM-GM Inequality$$ \frac{n_1 n_2 \cdots n_a}{a} \geq \sqrt[a]{n_1 n_2 \cdots n_a} $$等号当且仅当 $n_1 n_2 \cdots n_a$ 时成立。推论一若拆分的数量 $a$ 确定则各拆分数字相等时乘积最大。也就是说讨论拆成多少个之前可以先假定每个拆分数字都等于同一个因子 $x$。2.2 第二步转化为单变量极值问题设将数字以因子 $x$ 等分为 $a$ 个即 $n ax$则乘积为 $x^a$。由于 $n$ 是常数可以做如下恒等变形$$ x^a x^{\frac{n}{x}} \left(x^{\frac{1}{x}}\right)^n $$因为 $n$ 固定所以当 $x^{\frac{1}{x}}$ 取最大值时乘积达到最大值。问题被转化为求函数 $y x^{\frac{1}{x}}$ 的极大值。2.3 对 x 求导找到极值点文档给出了完整求导过程先取对数再对 $x$ 求导$$ \begin{aligned} \ln y \frac{1}{x} \ln x \text{取对数} \ \frac{1}{y} \dot{y} \frac{1}{x^2} - \frac{1}{x^2} \ln x \frac{1 - \ln x}{x^2} \text{对 $x$ 求导} \ \dot{y} \frac{1 - \ln x}{x^2} x^{\frac{1}{x}} \text{整理得} \end{aligned} $$令 $\dot{y} 0$则 $1 - \ln x 0$易得驻点为$$ x_0 e \approx 2.7 $$根据导数的符号变化可知 $x_0$ 为极大值点$$ \dot{y}\begin{cases} 0 , x \in (-\infty, e) \ 0 , x \in (e, \infty] \end{cases} $$2.4 因子必须是整数在 2 和 3 之间比较由于拆分因子 $x$ 必须为整数最接近 $e$ 的整数是 $2$ 或 $3$。分别代入$$ y(3) 3^{1/3} \approx 1.44 \ y(2) 2^{1/2} \approx 1.41 $$文档还给出一个口算对比方法给两数字同时取 $6$ 次方再对比整数大小——$$ [y(3)]^6 (3^{1/3})^6 9 \ [y(2)]^6 (2^{1/2})^6 8 $$因为 $9 8$所以 $y(3) y(2)$即 $x 3$ 时乘积最大。推论二将数字 $n$ 尽可能以因子 $3$ 等分时乘积最大。三、拆分规则与算法流程3.1 三条拆分规则由推论二可以直接归纳出贪心拆分的三条规则文档原文最优3。把数字 $n$ 尽可能拆为多个因子 $3$余数可能为 $0, 1, 2$ 三种情况。次优2。若余数为 $2$则保留不再拆为 $1 1$因为 $1 \times 1 2$。最差1。若余数为 $1$则应把一份 $3 1$ 替换为 $2 2$因为 $2 \times 2 3 \times 1$。3.2 算法流程文档给出了 O(1) 的分情况讨论流程当 $n \leq 3$ 时按照规则本应不拆分但题目要求必须拆成至少两个正整数因此必须拆出一个因子 $1$即返回 $n - 1$。当 $n 3$ 时求 $n$ 除以 $3$ 的整数部分 $a$ 和余数部分 $b$即 $n 3a b$分为三种情况当 $b 0$ 时直接返回 $3^a$当 $b 1$ 时要将一个 $1 3$ 转换为 $2 2$因此返回 $3^{a-1} \times 4$当 $b 2$ 时返回 $3^a \times 2$。边界验证$n 2, 3$ 时返回 $n - 1$$n 2$唯一拆分 $1 1$乘积 $1$恰好等于 $2 - 1$$n 3$拆分 $1 2$乘积 $2$恰好等于 $3 - 1$若拆成 $111$ 乘积只有 $1$。对于 $n 3$ 的常规情况例如 $n 10$$a 3, b 1$答案为 $3^{2} \times 4 36$对应的拆分为 $3 3 2 2$。该用例在仓库的驱动代码中已给出见下文。3.3 复杂度分析文档给出的复杂度结论时间复杂度 $O(1)$仅有求整、求余、次方运算。空间复杂度 $O(1)$a和b使用常数大小额外空间。需要说明的是求整、求余、幂运算为 $O(1)$ 的前提是数字在机器数范围内如 32/64 位整数此时 CPU 一条指令即可完成若涉及任意精度大整数则需按位运算重新考量。文档亦通过外部资料佐证了该结论不超过机器数的整数取模可视为 $O(1)$浮点取幂Math.pow底层 C 库实现同样可视为 $O(1)$。四、多语言实现仓库源码对照4.1 Python 实现仓库中的 lc_343_integer_break.py 与文档代码完全一致from include import * # Solution Code class Solution: def integerBreak(self, n: int) - int: if n 3: return n - 1 a, b n // 3, n % 3 if b 0: return int(math.pow(3, a)) if b 1: return int(math.pow(3, a - 1) * 4) return int(math.pow(3, a) * 2)关于幂运算的选择文档特别强调Python 中常见有三种幂计算函数——**幂运算符和pow()的时间复杂度均为 $O(\log a)$math.pow()始终调用 C 库的pow()函数执行浮点取幂时间复杂度为 $O(1)$。因此本题为了达到严格的 $O(1)$ 时间应使用math.pow(3, a)而非3 ** a或pow(3, a)。4.2 Java 实现仓库中的 lc_343_integer_break.java 与文档代码一致package lc_343_integer_break; import include.*; import java.util.*; // Solution Code class Solution { public int integerBreak(int n) { if(n 3) return n - 1; int a n / 3, b n % 3; if(b 0) return (int)Math.pow(3, a); if(b 1) return (int)Math.pow(3, a - 1) * 4; return (int)Math.pow(3, a) * 2; } }Java 的Math.pow(3, a)底层调用 C 库浮点取幂同样满足 $O(1)$随后用(int)强转回整数返回。4.3 仓库中同源题目的扩展剪绳子系列该解法并非孤例在仓库的《剑指 Offer》目录中可找到同源题目与变体可以交叉印证算法正确性剑指 Offer 14-I 剪绳子Python、Java、C与本题逻辑完全相同其中 C 版本使用pow(3, a)与int返回测试用例n 10输出36#include ../include/include.hpp class Solution { public: int cuttingRope(int n) { if (n 3) return n - 1; int a n / 3, b n % 3; if (b 0) return pow(3, a); if (b 1) return pow(3, a - 1) * 4; return pow(3, a) * 2; } };剑指 Offer 14-II 剪绳子 IIPython 大数版当 $n$ 极大时$3^a$ 会溢出机器数。Python 因语言特性可天然处理大整数只需对结果取模 $1000000007$class Solution: def cuttingRope(self, n: int) - int: if n 3: return n - 1 a, b, p n // 3, n % 3, 1000000007 if b 0: return 3**a % p if b 1: return 3 ** (a - 1) * 4 % p return 3**a * 2 % p注意此处a很大使用3 ** a整型幂运算$O(\log a)$而非math.pow浮点会丢精度可见两种幂函数在不同场景下各有用途。五、解法对比与总结5.1 为什么贪心拆 3 优于 DP本题在 LeetCode 官方题解中属于动态规划分类dp[i] max(j * (i - j), j * dp[i - j])复杂度 $O(n^2)$而本文基于数学推导的贪心解法只需要常数次求整、求余、取幂复杂度为 $O(1)$。从源码结构看仓库为本题提供了单一的最优数学解法文件Python 与 Java 各一份而在其他多解法题目中仓库会以_s1、_s2后缀保留多个实现这从侧面印证了拆 3 分情况讨论是该题最推荐的方案。5.2 算法要点速记情形返回值对应拆分$n \leq 3$$n - 1$必须拆分拆出因子 $1$$n 3,\ b 0$$3^a$$3 3 \cdots 3$$n 3,\ b 1$$3^{a-1} \times 4$$3 \cdots 3 2 2$合并 $31$$n 3,\ b 2$$3^a \times 2$$3 \cdots 3 2$5.3 一句话总结本题的完整推理链为均值不等式 → 均分最优 → 求 $x^{1/x}$ 极值 → 驻点 $e$ → 整数因子取 $3$ → 按余数 $0/1/2$ 分情况讨论。这套先证明结构、再贪心落码的思路不仅让integerBreak能以 O(1) 时间求解也直接迁移到剪绳子 I/II 等变体题目中是笔试面试中数学贪心类问题的经典范式。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考