剑指offer13_剪绳子

剪绳子

---

给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n都是整数，2≤n≤58 并且 m≥2）。

每段的绳子的长度记为 k[1]、k[2]、……、k[m]。

k[1]k[2]…k[m] 可能的最大乘积是多少？

例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。

样例

输入：8输出：18

---

整数拆分最大乘积问题（数学归纳与证明）

问题描述

给定正整数 $N\ge 2$，将其拆分为若干正整数的和：
N=n1​+n2​+⋯+n**k​(k≥2)
求最大化乘积 $P=n_1\times n_2\times \cdots \times n_k$

数学证明

引理1：拆分中不含1

若存在 $n_i=1$，设剩余部分和为 $S$，则乘积 $P=1\times S=S$
但 $S=N-1$，而直接拆分 $N=(N-1)+1$ 的乘积为 $N-1<N$
矛盾！故拆分中不含1

引理2：拆分中不含≥5的数

若存在 $n_i\ge 5$，将其拆分为 $3+(n_i-3)$：
3×(ni−3)=3ni−9>ni(∵ni≥5⇒2ni>9)
新拆分乘积更大，矛盾！故拆分中不含≥5的数

引理3：拆分中不含4

若存在 $n_i=4$，可拆分为 $2+2$：
2×2=4=ni​
乘积不变但增加拆分项数，为后续优化创造条件

引理4：至多两个2

若有三个2（$2\times 2\times 2=8$），替换为两个3：
3×3=9>8
乘积更大，故拆分中至多两个2

定理：最优解结构

由引理1-4，最优拆分仅含 2 和 3，且满足：

1. $3$ 的数量尽可能多
2. $2$ 的数量为 0, 1, 2
3. 当余数为1时，需将一组 $3+1$ 替换为 $2+2$

构造性证明

设 $N=3k+r$，其中 $r=N\mathrm{m}\mathrm{o}\mathrm{d}3\in 0,1,2$

$r$	拆分方案	最大乘积
0	$k$ 个 $3$	$3^k$
1	$(k-1)$ 个 $3$ + $2$ 个 $2$	$3^{k-1}\times 4$
2	$k$ 个 $3$ + $1$ 个 $2$	$3^k\times 2$

特殊边界处理：

• $N=2$：强制拆分为 $1+1$（乘积1）
• $N=3$：强制拆分为 $1+2$（乘积2）

时间复杂度分析

1. 计算 $k=\lfloor N/3\rfloor$：$O(1)$
2. 计算余数 $r=N\mathrm{m}\mathrm{o}\mathrm{d}3$：$O(1)$
3. 乘积计算：
   • 直接公式计算：$O(1)$
   • 若模拟拆分过程：$O(k)=O(N/3)=O(N)$

数学解释

为什么是3？

函数 $f(x)=(N/x{)}^x$ 的极大值点在 $x=N/e$ 附近
$\because e\approx 2.718\Rightarrow$ 最接近整数为3

数值验证

$N$	最优拆分	乘积	公式计算
2	$1+1$	1	1
3	$1+2$	2	2
4	$2+2$	4	4
5	$2+3$	6	6
6	$3+3$	9	9
7	$3+2+2$	12	12
8	$3+3+2$	18	18
9	$3+3+3$	27	27
10	$3+3+2+2$	36	36

扩展思考

1. 连续实数拆分：当拆分数 $k\to \infty$，乘积收敛于 $e^{N/e}$
2. 约束拆分：若限定 $n_i\le m$，问题转化为背包问题
3. 几何解释：在 $\sum n_i=N$ 约束下求 $\prod n_i$ 极大值，最优解位于均值附近

---

题解

class Solution {
public:int maxProductAfterCutting(int n) {if(n <= 3) return 1 * (n - 1);int res = 1;if(n % 3 == 1) res = 4, n -= 4;if(n % 3 == 2) res = 2, n -= 2;while(n) res *= 3, n -= 3;return res;}
};