題⽬描述

給你⼀根⻓度為 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)，只使用固定變量