LeetCode 剑指 Offer 14- I. 剪绳子

约 4 分钟
文章信息 12 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 美团 阿里巴巴 京东 拼多多 剑指 Offer 剑指 Offer（第 2 版）
标签
动态规划 数学
目录

题目描述

✅ 剑指 Offer 14- I. 剪绳子

image-20241107204856095

题意分析

输入是一根长度为 $n$ 的整数长度绳子，要求剪成至少两段，每段长度都是正整数，输出这些段长度乘积的最大值。

「至少两段」是最强的约束信号：它意味着不允许「一刀不剪」，所以答案并不是 $n$ 本身。当 $n$ 很小、小到剪一刀反而亏的时候，我们仍然必须剪，这就制造了两个必须单独处理的边界。

数据范围 $2 \le n \le 58$ 也是一个信号。它小到可以用一个长度为 $n + 1$ 的数组做递推，同时最大答案（$n = 58$ 时为 $3^{18} \times 4 = 1549681956$）仍然落在 32 位有符号整数范围内，因此不需要取模，也不需要大数。这一点和「剪绳子 II」正好相反。

需要单独确认的边界有三个：$n = 2$ 只能剪成 1 + 1，答案是 1；$n = 3$ 只能剪成 1 + 2 或 1 + 1 + 1，答案是 2；而从 $n = 4$ 开始，剪一刀就不再吃亏（2 + 2 得到 4，正好等于 $n$），之后剪得越合理乘积增长越快。

另外要注意「相同长度的段可以重复出现」，题目没有要求各段互不相同，所以最优解通常是一堆相同的小段。

解法：贪心优先剪出长度 3

核心思路

对任意长度 x >= 5，把它拆成 3 和 x - 3 后，乘积满足 3(x - 3) > x，因此最优答案中不会保留长度大于等于 5 的整段。最终只需考虑 2、3、4。

在相同总长度下，3 比 2 更适合作为主要因子：3 × 3 = 9 > 2 × 2 × 2 = 8。所以应尽量剪出 3，但不能留下 1；若余数为 1，应把最后的 3 + 1 改成 2 + 2，因为 4 大于 3。

循环条件写成 n > 4，每次剪出一个 3。退出时剩余长度只能是 2、3 或 4：2、3 可作为最后一段，4 对应 2 × 2，数值仍是 4。这样余 1 的情况会自然调整为 4。

解题步骤

  1. n <= 3 时必须剪一刀，返回 n - 1。
  2. 初始化乘积 result = 1。
  3. 当剩余长度大于 4 时，剪出一段 3：result *= 3、n -= 3。
  4. 将最后的 2、3 直接乘入结果；剩余 4 时按 2 × 2 理解，乘积同样是 4。

例如 n = 10：连续剪出两个 3，剩余 4，得到 3 × 3 × 4 = 36，等价于 3 + 3 + 2 + 2。

代码实现

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)$。循环每次将剩余长度减少 3；在本题 n <= 58 时轮数很少。
  • 空间复杂度：$O(1)$。只使用常数个变量。

关键点总结

  • “至少剪成两段”使 n = 2、3 必须返回 n - 1，不能直接返回 n。
  • 长度大于等于 5 的段继续拆出 3 会严格增大乘积。
  • 尽量使用 3，但绝不能留下 1；3 + 1 应调整为 2 + 2。
  • 保留最后的 4，可用一个 n > 4 的循环统一处理余数，无需分类代码。

易错点总结

  • n <= 3 时返回 n，等价于没有剪绳子，违反题意。
  • 循环写成 n >= 4 会把剩余 4 拆成 3 + 1，乘积反而变小。
  • 始终剪 2 并非最优，例如长度 6 时 3 × 3 > 2 × 2 × 2。
  • 本题不要求取模；不要直接套用“剪绳子 II”的代码。

相似题目

题目 难度 考察点
343. 整数拆分 中等 整数拆分求最大乘积
279. 完全平方数 中等 拆分为完全平方数之和
剑指 Offer 14- II. 剪绳子 II 中等 大数取模与快速幂