思路解答动态规划自底向上计算最优解javapublic 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 ij × (i-j)剪一刀的情况j × dp[i-j]剪多刀的情况javapublic 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⽐如text2 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 3javapublic 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凑成为 44 分段之后的最⼤乘积也是 42 * 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.7183是最接近的整数4的特殊处理2×2 3×1所以剩余4时剪成2×2而不是3×1执行过程示例n10text10 ÷ 3 3段...剩余1 调整2段3 → 剩余4 → 剪成2×2 结果3² × 2² 9 × 4 36在计算幂次⽅的时候为了避免溢出在每次相乘的时候都需要除以998244353 ,为了计算快每次以⾃身相乘的⽅式计算代码如下javapublic 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; }
剑指offer-71、剪绳子（进阶版）
思路解答动态规划自底向上计算最优解javapublic 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 ij × (i-j)剪一刀的情况j × dp[i-j]剪多刀的情况javapublic 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⽐如text2 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 3javapublic 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凑成为 44 分段之后的最⼤乘积也是 42 * 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.7183是最接近的整数4的特殊处理2×2 3×1所以剩余4时剪成2×2而不是3×1执行过程示例n10text10 ÷ 3 3段...剩余1 调整2段3 → 剩余4 → 剪成2×2 结果3² × 2² 9 × 4 36在计算幂次⽅的时候为了避免溢出在每次相乘的时候都需要除以998244353 ,为了计算快每次以⾃身相乘的⽅式计算代码如下javapublic 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; }
