AcWing刷题笔记-25-剪绳子

题目信息

平台：AcWing
难度：中等
题目链接：剪绳子

题目描述

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n 都是整数，n > 1 并且 m > 1），每段绳子的长度记为 k[0], k[1]...k[m-1] 。请问 k[0] * k[1] * ... * k[m-1] 可能的最大乘积是多少？

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

初步思路

这道题乍一看可以用动态规划来做：设 dp[i] 表示长度为 i 的绳子剪成若干段后的最大乘积，然后枚举第一段的长度进行转移。

不过，这题其实有一个非常漂亮的数学规律，可以写出 O(1) 的贪心解法。

算法分析

核心思想：贪心，当 n >= 5 时，尽可能拆分成多个 3，乘积最大
技巧要点：注意 n % 3 == 1 的特殊处理，此时拆成两个 2 比拆成一个 3 和一个 1 更优
时间复杂度：O(n)（循环累乘）
空间复杂度：O(1)

数学推导

关键推断：当 n >= 5 时，把 n 拆成 3 + (n - 3)，乘积 3 * (n - 3) > n。

这意味着只要长度还大于等于 5，拆出一个 3 就能让乘积变大。所以最优策略就是不断拆 3。

但是有三种边界情况需要单独处理：

情况	条件	拆分方式
情况 1	`n % 3 == 0`	直接拆成 `n / 3` 个 `3`
情况 2	`n % 3 == 1`	拆成 `n / 3 - 1` 个 `3` 和一个 `4`（即两个 `2`）
情况 3	`n % 3 == 2`	拆成 `n / 3` 个 `3` 和一个 `2`

为什么情况 2 要这样处理？ 如果余数是 1，那么剩下一个 1 很亏（乘以 1 不增反降），不如从之前拆的 3 里拿出一个来，凑成 3 + 1 = 4，拆成 2 * 2 = 4，这样更优。

代码实现（C++）

class Solution {
public:
    int maxProductAfterCutting(int length) {
        // 长度小于等于 3 时，必须至少剪一刀，所以最优是剪成 1 和 length-1
        if (length <= 3) return 1 * (length - 1);

        int res = 1;

        // 处理余数为 1 的情况：先拆出一个 4（相当于两个 2）
        if (length % 3 == 1) {
            length -= 4;
            res = 4;
        }
        // 处理余数为 2 的情况：先拆出一个 2
        else if (length % 3 == 2) {
            length -= 2;
            res = 2;
        }
        // 余数为 0 时直接全部拆成 3

        // 剩下的长度全是 3 的倍数，不断拆 3
        while (length) {
            res *= 3;
            length -= 3;
        }
        return res;
    }
};

测试用例

输入	输出	说明
`2`	`1`	只能剪成 `1 + 1`，乘积为 `1`
`3`	`2`	剪成 `1 + 2`，乘积为 `2`
`4`	`4`	剪成 `2 + 2`，乘积为 `4`，比 `1 + 3` 更优
`8`	`18`	剪成 `2 + 3 + 3`，乘积为 `18`
`10`	`36`	剪成 `3 + 3 + 2 + 2`，乘积为 `36`

总结与反思

核心结论就是：**尽可能拆成 3**。

不过在实际编码时，边界情况容易踩坑——尤其是 n <= 3 时必须至少剪一刀，以及 n % 3 == 1 时要把一个 3 和余下的 1 凑成 4 来处理。

TK的小站