LeetCode 剑指 Offer 14- II. 剪绳子 II
目录
题目描述
题意分析
一根长度为 $n$ 的绳子，要剪成 $m$ 段（$m>1$，也就是至少剪一刀），每段长度都是正整数，求各段长度乘积的最大值，结果对 $1000000007$ 取模。
「$m>1$」这个约束单独作用在小规模输入上：$n=2$ 只能剪成 $1+1$，乘积是 1，不能不剪；$n=3$ 只能剪成 $1+2$ 或 $1+1+1$，最大乘积是 2，同样不能保留完整的 3。这两项必须写死，任何通用公式套上去都会给出偏大的答案。
最关键的约束信号是那句取模。上一题「剪绳子 I」中 $n \le 58$，乘积可以用 64 位整数直接装下；这里 $n$ 可以到 1000，最优解形如 $3^{333}$，位数三位数级别，别说
long，连大整数都不适合反复比较。而一旦对结果取模，数值之间的大小关系就被彻底打乱了——模意义下 $a$ 比 $b$ 大，完全不代表真实的 $a$ 比 $b$ 大。这就直接封死了「先动态规划求最大值、再顺手取模」这条路，逼你先在数学上把最优结构推清楚，再照着构造答案。边界要列全：$n=2$ 返回 1，$n=3$ 返回 2；$n$ 被 3 整除、余 1、余 2 三种情况的处理方式各不相同；快速幂的指数可能为 0（此时应返回 1）。
解法：贪心 + 快速幂
核心思路
先看看动态规划为什么走不通。定义 $f[i]$ 为长度 $i$ 的绳子剪开后的最大乘积，转移是枚举第一刀的位置 $j$，取 $\max\big(j\cdot(i-j),\ j\cdot f[i-j]\big)$ 的最大值，时间 $O(n^2)$。在剪绳子 I 里这是标准答案，但这里的 $f$ 值必须取模才能存下，而取模后的
max比较毫无意义，整个 DP 的地基就塌了。所以瓶颈不是速度，是取模与求最值不兼容。既然不能比较，就得直接推出最优解的形状。分三步观察：
其一，任何一段长度 $x \ge 5$ 都应该继续切。把它切成 $3$ 和 $x-3$，乘积变成 $3(x-3)$，而 $3(x-3) > x$ 等价于 $3x-9>x$ 即 $x>4.5$，所以 $x\ge 5$ 时切一刀严格更优。反复应用可知，最优解里每段长度都不超过 4。
其二，长度 4 可以拆成 $2+2$，乘积 $2\times 2=4$ 与不拆完全相同，所以不妨把 4 也拆掉。于是最优解的段长只可能是 2 和 3（长度 1 显然是浪费，它只会让乘积变小）。
其三，2 最多出现两个。因为三个 2 的和是 6，乘积是 8；同样用掉 6 的长度换成两个 3，乘积是 9，严格更大。所以只要凑齐三个 2 就该换成两个 3。
三条合起来给出唯一的最优结构：尽量多切 3，剩下的零头按 $n \bmod 3$ 分三种情况处理。余数为 0 时全是 3；余数为 2 时全切 3 后额外留一段 2；余数为 1 时不能留一段 1（乘以 1 是浪费），要退回一个 3，把 $3+1$ 重新组织成 $2+2$。写成公式就是答案等于 $3^a\cdot b$，其中 $(a,b)$ 由 $n\bmod 3$ 决定：余 0 取 $(n/3,\,1)$，余 1 取 $(n/3-1,\,4)$，余 2 取 $(n/3,\,2)$。
最后只剩计算问题。指数 $a$ 最大约 333，直接循环乘 333 次其实也够快，但标准写法是快速幂：把指数按二进制拆开，每一位对应底数的一次平方，$O(\log a)$ 次乘法即可，且每次乘完立刻取模，全程不会溢出。
解题步骤
- 先特判 $n \le 3$，直接返回 $n-1$。为什么是 $n-1$：$n=2$ 时只能切成 $1+1$ 得 1，$n=3$ 时最优是 $1+2$ 得 2，恰好都等于 $n-1$；这一段之所以要写死，是因为「至少剪一刀」让它们脱离了通用规律。
- 令 $a=n/3$、$b=n\bmod 3$，作为「切出 $a$ 段 3、剩下 $b$」的初始方案。为什么以 3 为单位：由前面的推导，最优解中除零头外全部是 3。
- 若 $b=1$，则令 $a$ 减一、$b$ 置为 4。为什么要退一步：剩下长度 1 只能单独成段，乘上 1 等于白扔；退回一个 3 与它合成 4，再拆成 $2\times 2=4$，比 $3\times 1=3$ 大。
- 若 $b=0$，则令 $b=1$。为什么不是 0：这里的 $b$ 是要乘进答案的因子，没有零头时因子应为乘法单位元 1，写成 0 会把整个答案清零。余数为 2 时保持 $b=2$ 不变，因为单独留一段 2 就是最优。
- 用快速幂在模意义下算出 $3^a$，再乘以 $b$ 并取模返回。为什么乘完还要取模：$3^a \bmod p$ 最大接近 $10^9$，乘上最大为 4 的 $b$ 会达到 $4\times 10^9$，超出 32 位范围，必须用 64 位承接并再取一次模。
- 快速幂内部：结果初始化为 1，底数先对模数取余；每轮检查指数最低位，为 1 就把当前底数乘进结果并取模，然后底数自乘取模、指数右移一位，直到指数为 0。为什么每步都取模：模乘的性质保证 $(x\cdot y)\bmod p=\big((x\bmod p)(y\bmod p)\big)\bmod p$，逐步取模不改变结果，却能把中间量始终压在 $10^9$ 以内，两数相乘不超过 $10^{18}$，恰好落在 64 位范围内。
以
n = 10走一遍：$10>3$ 不走特判。$a=10/3=3$，$b=10\bmod 3=1$。余数为 1，触发回退：$a$ 变成 2，$b$ 变成 4，此时的切法是「两段 3 加两段 2」，长度校验 $3+3+2+2=10$ 正确。接着算 $3^2 \bmod (10^9+7)$：初始res = 1、cur = 3、e = 2；第一轮e的最低位是 0，不乘进结果，cur自乘变成 9，e右移成 1；第二轮e的最低位是 1，res = 1 × 9 = 9，cur自乘变成 81，e右移成 0，循环结束，返回 9。最后 $9\times 4 \bmod (10^9+7)=36$。手工核对：$3\times 3\times 2\times 2=36$，而若不回退直接用 $3\times 3\times 3\times 1=27$，确实更小，回退这一步是必要的。再快速核对另外两类余数。$n=6$：$a=2$、$b=0$，把 $b$ 置为 1，答案 $3^2\times 1=9$，对应切法 $3+3$，优于 $2+2+2=8$。$n=5$：$a=1$、$b=2$，答案 $3^1\times 2=6$，对应切法 $3+2$，优于 $2+2+1=4$ 和 $4+1=4$。
代码实现
// 若余数为 1，则把一个 3 改成 2+2。
class Solution {
private static final int MOD = 1_000_000_007;
public int cuttingRope(int n) {
if (n <= 3) {
return n - 1;
}
int a = n / 3;
int b = n % 3;
if (b == 1) {
a--;
b = 4;
} else if (b == 0) {
b = 1;
}
long pow = fastPow(3, a);
return (int) (pow * b % MOD);
}
private long fastPow(long base, int exp) {
long res = 1;
long cur = base % MOD;
int e = exp;
while (e > 0) {
if ((e & 1) == 1) {
res = res * cur % MOD;
}
cur = cur * cur % MOD;
e >>= 1;
}
return res;
}
}
// 若余数为 1，则把一个 3 改成 2+2。
func cuttingRope(n int) int {
const mod int64 = 1_000_000_007
if n <= 3 {
return n - 1
}
a := n / 3
b := n % 3
if b == 1 {
a--
b = 4
} else if b == 0 {
b = 1
}
pow := fastPow(3, a, mod)
return int(pow * int64(b) % mod)
}
func fastPow(base int64, exp int, mod int64) int64 {
res := int64(1)
cur := base % mod
for exp > 0 {
if exp&1 == 1 {
res = res * cur % mod
}
cur = cur * cur % mod
exp >>= 1
}
return res
}
复杂度分析
- 时间复杂度：$O(\log n)$，凭据：段数的划分只是几次整除和取余，代价是常数；真正的循环在快速幂里，指数 $a\approx n/3$ 每轮右移一位，轮数为 $\lfloor\log_2 a\rfloor+1$，每轮只有常数次乘法和取模。
- 空间复杂度：$O(1)$，凭据：只用了 $a$、$b$、结果、底数、指数这几个标量，快速幂写成迭代形式后连递归栈都没有，不随 $n$ 增长。
关键点总结
- 「结果要取模」往往等价于「不能用动态规划求最值」。模运算破坏序关系，凡是转移里出现
max或min且状态值必须取模的题，都要先怀疑题目是否在暗示存在闭式解或数学结论。- 贪心结论要能现场证出来，不能背。本题三步论证——段长不超过 4、4 等价于两个 2、三个 2 不如两个 3——每一步都是一行不等式，面试时把它们说出来比直接甩结论有说服力得多。
- 余数为 1 时必须回退一个 3。乘以 1 永远是浪费，这类「零头不能单独成段」的调整在整数拆分类问题里反复出现。
- 用作乘法因子的变量，其「什么都没有」的取值是 1 而不是 0。把余数 0 改写成因子 1 是本题最容易被忽略的一行。
- 面试视角：先问清楚是剪绳子 I 还是 II。同一道题只差一个取模，解法却从 $O(n^2)$ 的 DP 换成 $O(\log n)$ 的数学构造；能主动指出这个差异，说明真的读懂了约束而不是背了模板。
- 面试视角：快速幂几乎必被追问原理。要能说清「指数二进制拆分」和「每步取模不改变结果」这两点，并顺带说明为什么 64 位足够——因为中间量都小于 $10^9+7$，两数相乘不超过 $10^{18}$，没有溢出风险。
易错点总结
- 错误写法：照搬剪绳子 I 的动态规划，在转移里对状态取模后继续用
max比较。用例 $n=1000$ → 取模把真实大小关系打乱，max选出的往往不是真正最大的方案，答案错得毫无规律且难以定位。- 错误写法：不特判 $n\le 3$，直接套 $3^a\cdot b$ 的公式。用例 $n=3$ → 得 $a=1$、$b=0$ 改为 1，算出 3，但题目要求至少剪一刀，正确答案是 2。
- 错误写法：余数为 1 时不回退，直接乘上零头 1。用例 $n=10$ → 得到 $3\times3\times3\times1=27$，而把一个 3 与这个 1 合成 $2+2$ 可得 36，少算了近三成。
- 错误写法：余数为 0 时把因子 $b$ 保留为 0。用例 $n=6$ → 答案变成 $9\times 0=0$，直接归零。
- 错误写法：用浮点函数计算幂，例如
Math.pow(3, a)再取模。用例 $a$ 稍大一些 → 双精度只有约 15 位有效数字，$3^{333}$ 早已超出精确表示范围，得到的整数部分完全是噪声。- 错误写法：快速幂中用 32 位整数存放中间结果。用例任意使
res和cur都接近 $10^9$ 的输入 → 乘积接近 $10^{18}$，int立刻回绕成负数，后续取模全错；必须用 64 位承接乘积。- 错误写法：快速幂只在最后取一次模。用例 $a=333$ → 底数平方 333 轮，数值早就突破 64 位，溢出后的值毫无意义。
- 错误写法：最后一步写成
(int) pow * b % MOD。用例 $b=4$ 且pow接近 $10^9$ → 强制转换先把pow截成int，随后int乘法溢出；正确写法是在 64 位下完成pow * b % MOD之后再转换。- 错误写法：认为全切 2 也一样好，于是按 $n\bmod 2$ 分情况。用例 $n=6$ → 得到 $2\times2\times2=8$，而 $3\times3=9$ 更大；只有在长度不足以切出 3 时才轮到 2。
- 错误写法：把快速幂的指数为 0 的情形漏掉，让循环至少执行一次。用例 $n=4$（此时 $a=0$、$b=4$）→ 若强行乘一次底数会得到 $3\times 4=12$，而正确答案是 $2\times 2=4$；指数为 0 时结果必须是 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 50. Pow(x, n) | 中等 | 快速幂本体，还要处理负指数与最小值溢出 |
| 343. 整数拆分 | 中等 | 同一贪心结论，但无需取模，可直接对拍验证 |
| 372. 超级次方 | 中等 | 指数以数组形式给出，需按位递归做模幂 |
| 剑指 Offer 14- I. 剪绳子 | 中等 | 不取模，可用 $O(n^2)$ 动态规划，适合对照差异 |
| 剑指 Offer 16. 数值的整数次方 | 中等 | 快速幂换皮，重点在指数取反时的边界处理 |