当前位置：首页 > news >正文

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

news 2026/3/27 2:20:07

题⽬描述

给你⼀根⻓度为 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？

数学证明：当n ≥ 5时，3(n-3) ≥ 2(n-2) > n
接近自然底数e：最优分段长度应接近e ≈ 2.718，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;}
}