思路解答
动态规划
自底向上计算最优解
java
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]：剪多刀的情况
java
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
⽐如：
text
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
java
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）：
text
10 ÷ 3 = 3段...剩余1 调整：2段3 → 剩余4 → 剪成2×2 结果：3² × 2² = 9 × 4 = 36
在计算幂次⽅的时候，为了避免溢出，在每次相乘的时候，都需要除以998244353 ,为了计算快，每次以⾃身相乘的⽅式计算，代码如下：
java
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; }
