LeetCode 剑指 Offer 14- I. 剪绳子
题目描述
题意分析
将长度为
n的绳子剪成至少两段，每段长度都是正整数，求各段长度乘积的最大值。所有段的长度之和必须仍为n。至少剪一刀是硬性要求，不能直接用整条绳子的长度作为答案。特别是长度二和三，虽然不剪更大，仍要返回剪开后的最大乘积。本题范围为
2 <= n <= 58，答案使用整数返回，不需要取模。
解法：贪心优先剪出长度 3
核心思路
[!blue]
先分析最优方案里会有哪些长度。对任意一段 $x\ge5$，拆成 $3$ 和 $x-3$ 后，乘积为 $3(x-3)$，与不拆相比增加 $2x-9>0$。因此最优方案不会保留大于等于五的段。
当总长至少为四时，也没必要保留长度一：它与长度二可以合成三以增大乘积；与长度三可以换成两个二；与长度四可以换成二和三；两个一也可以合成二。所以最优方案只需要长度二、三，以及等价于两个二的四。
剩下只需决定二和三的比例。同样总长六，三个二的乘积是八，两个三的乘积是九，所以三个二总能换成两个三而变得更优。最优方案应尽量用三，最多保留两个二。
因此每次从剩余长度中取出三，但不能留下长度一。代码只在
n > 4时继续取三，最后剩下二、三或四，直接乘入结果。剩四代表拆成两个二，乘积恰好也是四；这并不违反至少剪成两段的要求。对
n = 2、n = 3，上述“避免一”的调整无法同时满足至少两段，需要单独返回n - 1。
解题步骤
- 若
n <= 3，返回n - 1，满足必须剪开。- 初始化已经剪出部分的乘积
result = 1。- 只要剩余长度
n > 4，就剪出一段三，将result乘三并将n减三。- 返回
result * n；最后剩四时按两个二的乘积理解。
代码实现
class Solution {
public int cuttingRope(int n) {
if (n <= 3) {
return n - 1;
}
int result = 1;
// 剩四时保留为二乘二，避免拆成三加一而降低乘积。
while (n > 4) {
result *= 3;
n -= 3;
}
return result * n;
}
}
func cuttingRope(n int) int {
if n <= 3 {
return n - 1
}
result := 1
// 剩四时保留为二乘二，避免拆成三加一而降低乘积。
for n > 4 {
result *= 3
n -= 3
}
return result * n
}
复杂度分析
- 时间复杂度：$O(n)$，每次循环将剩余长度减少三。
- 空间复杂度：$O(1)$，只维护剩余长度和乘积。
关键点总结
[!green]
- 通过替换证明排除长段和长度一，再比较同总长的二与三。
- 三优先，但余一需要改成两个二，不能机械地一直剪三。
- 只在剩余长度大于四时继续，统一处理所有余数情况。
解法：动态规划枚举第一段
核心思路
[!blue]
也可以不预先推导最优段长，而是直接枚举切法。令
dp[length]表示长度为length的绳子至少剪一刀后，能够得到的最大乘积。枚举第一段长度
first，范围是1..length-1，剩余部分长度为length-first。第一段作为完整的一段保留，剩余部分可以不再剪，贡献它本身的长度；也可以继续剪，贡献对应的dp值。因此这次选择的最优乘积为first * max(length-first, dp[length-first])。任意合法切法都有一个第一段，剩余部分正好属于上述“不剪”或“继续剪”两类。枚举所有第一段并取最大值，就不会遗漏最优方案，也不需要再枚举左段内部切法。
dp[0]、dp[1]保持零，表示无法剪成两段；从长度二开始递增计算，右段总比当前绳子短，所需状态已经算好。第一刀由first < length保证，子段允许不再剪则由转移中的原长度保证。
解题步骤
- 创建长度为
n + 1的全零数组dp。- 按长度从二到
n依次计算。- 对每个长度枚举第一段，比较右段不剪与继续剪的乘积贡献。
- 用所有选择的最大乘积更新当前状态，最终返回
dp[n]。
代码实现
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n + 1];
for (int length = 2; length <= n; length++) {
for (int first = 1; first < length; first++) {
int rest = length - first;
dp[length] = Math.max(dp[length], first * Math.max(rest, dp[rest]));
}
}
return dp[n];
}
}
func cuttingRope(n int) int {
dp := make([]int, n+1)
for length := 2; length <= n; length++ {
for first := 1; first < length; first++ {
rest := length - first
bestRest := rest
if dp[rest] > bestRest {
bestRest = dp[rest]
}
product := first * bestRest
if product > dp[length] {
dp[length] = product
}
}
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O(n^2)$，每个长度枚举一次全部第一段选择。
- 空间复杂度：$O(n)$，保存各长度的最优乘积。
关键点总结
[!green]
- 整条绳子必须剪开，与剪出的子段是否继续剪，是两个不同层次的要求。
- 第一段枚举保证至少两段，右段取原长度或 DP 值覆盖全部后续切法。
- 状态按长度递增计算，依赖总是较短的绳子。
易错点总结
[!yellow]
- 对长度二、三直接返回
n，等价于没有剪，违反至少两段的条件。- 贪心循环使用
n >= 4会把最后的四拆成三与一，降低乘积。- 动态规划中的
dp[i]表示必须剪开的最大乘积，不能让它无条件与未剪的i取大。- 转移时又不能强迫右段也剪开，需要比较右段原长度与它继续剪开的最优值。
- 本题没有取模要求，不要沿用剪绳子 II 的取模处理来计算或比较乘积。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 14- II. 剪绳子 II | 中等 | 最大乘积的拆分规律相同，原题范围更大且要取模，不能把取模后的值直接用于大小比较。 |