剑指offer-71、剪绳子（进阶版）

题⽬描述

给你⼀根⻓度为 n 的绳⼦，请把绳⼦剪成整数⻓的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳⼦的⻓度记为 k[1] ,..., k[m] 。请问 k[1] * k[2] * ... * k[m] 可能的最⼤乘积是多少？例如，当绳⼦的⻓度是 8 时，我们把它剪成⻓度分别为 2 、3 、3 的三段，此时得到的最⼤乘积是 18 。

由于答案过⼤，请对 998244353 取模。

思路解答

动态规划

自底向上计算最优解

public class Solution {
    private static final int MOD = 998244353;
    
    public int cutRope(int n) {
        if (n < 2) return 0;
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        // dp[i]表示长度为i的绳子剪裁后的最大乘积
        long[] dp = new long[n + 1];
        
        // 基础情况：这些值不是乘积，而是长度本身（因为可以不剪）
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        
        // 从长度为4开始计算
        for (int i = 4; i <= n; i++) {
            long max = 0;
            // 遍历所有可能的分割点，j <= i/2 避免重复计算
            for (int j = 1; j <= i / 2; j++) {
                // 比较各种分割方案的乘积
                long product = dp[j] * dp[i - j];
                if (product > max) {
                    max = product;
                }
            }
            dp[i] = max % MOD;
        }
        
        return (int) dp[n];
    }
}

• 时间复杂度：O(n²)，外层循环n-3次，内层循环i/2次
• 空间复杂度：O(n)，需要dp数组存储中间结果

优化动态规划

在上面版本上优化状态转移方程，提高代码效率，直接比较j*(i-j)和j*dp[i-j]的最大值

dp[i] = max(max(j × (i-j), j × dp[i-j])) 其中 1 ≤ j < i

• j × (i-j)：剪一刀的情况
• j × dp[i-j]：剪多刀的情况

public class Solution {
    private static final int MOD = 998244353;
    
    public int cutRope(int n) {
        if (n < 2) return 0;
        if (n == 2) return 1;
        if (n == 3) return 2;
        
        long[] dp = new long[n + 1];
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // 三种情况取最大值：不剪、剪一刀、剪多刀
                long temp = Math.max(j * (i - j), j * dp[i - j]);
                dp[i] = Math.max(dp[i], temp);
            }
            dp[i] %= MOD;
        }
        
        return (int) dp[n];
    }
}

• 时间复杂度：O(n²)，双重循环
• 空间复杂度：O(n)，dp数组空间

贪心算法（最优解）

我们仔细观察就会发现：要想乘积⽐较⼤，在没有1的前提下，优先使⽤3，如果出现1，那么优先使⽤2

⽐如：

2 = 1 + 1
3 = 1 + 2
4 = 2 + 2
5 = 2 + 3
6 = 3 + 3
7 = 3 + 2 + 2
8 = 3 + 3 + 2
9 = 3 + 3 + 3
10 = 3 + 3 + 2 + 2
11 = 3 + 3 + 3 + 2
12 = 3 + 3 + 3 + 3

public class Solution {
    public long cutRope(long number) {
        if (number == 2) return 1;
        if (number == 3) return 2;
        long res = 1;
        while (number > 4) {
            res *= 3;
            res = res % 998244353;
            number -= 3;
        }
        return res * number % 998244353;
    }
}

结果很不幸：运⾏超时：您的程序未能在规定时间内运⾏结束，请检查是否循环有错或算法复杂度过⼤。

于是我们需要想到其他的⽅式，如何快速计算 3 的 n 次⽅，这是我们需要解决的问题，因为在尽量凑 3的前提下，有以下三种情况：

• 被 3 整除 等于 n ：直接计算 3 的 n 次幂
• 被 3 取余数为1，结果等于 n ：直接计算 3 的 （n-1） 次幂，再乘以4，为什么呢？因为余数是1，我们避免有1，需要借出 3，和 1凑成为 4，4 分段之后的最⼤乘积也是 4（2 * 2）
• 被 3 取余数为 2，结果等于 n：直接计算 3 的 n 次幂 ，再乘以2

也就是说，当n≥5时，优先剪出长度为3的段；剩余4时剪成2×2

为什么选择3？

1. 数学证明：当n ≥ 5时，3(n-3) ≥ 2(n-2) > n
2. 接近自然底数e：最优分段长度应接近e ≈ 2.718，3是最接近的整数
3. 4的特殊处理：2×2 > 3×1，所以剩余4时剪成2×2而不是3×1

执行过程示例（n=10）：

10 ÷ 3 = 3段...剩余1
调整：2段3 → 剩余4 → 剪成2×2
结果：3² × 2² = 9 × 4 = 36

在计算幂次⽅的时候，为了避免溢出，在每次相乘的时候，都需要除以998244353 ,为了计算快，每次以⾃身相乘的⽅式计算，代码如下：

public class Solution {
    private static final int MOD = 998244353;
    
    public int cutRope(int n) {
        // 特殊情况处理
        if (n <= 3) return n - 1;
        
        // 计算可以剪出多少段长度为3的绳子
        int countOf3 = n / 3;
        
        // 处理剩余部分：当剩余长度为1时，调整策略
        if (n - countOf3 * 3 == 1) {
            countOf3--; // 减少一段3，与剩余的1组成4
        }
        
        // 计算剩余部分能剪出多少段长度为2的绳子
        int countOf2 = (n - countOf3 * 3) / 2;
        
        // 计算结果：3的countOf3次方 × 2的countOf2次方
        long result = pow(3, countOf3) * pow(2, countOf2);
        return (int) (result % MOD);
    }
    
    /**
     * 快速幂算法计算a的b次方取模
     */
    private long pow(long a, long b) {
        long result = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                result = (result * a) % MOD;
            }
            a = (a * a) % MOD;
            b >>= 1;
        }
        return result;
    }
}

• 时间复杂度：O(1)，只有常数次操作
• 空间复杂度：O(1)，只使用固定变量