题目描述给你⼀根⻓度为n 的绳⼦请把绳⼦剪成整数⻓的m 段 m 、n 都是整数 n1 并 且m1 mn 每段绳⼦的⻓度记为k[1],...,k[m]。请问k[1]x...xk[m] 可能的最⼤乘积是多少例如当绳⼦的⻓度是8 时我们把它剪成⻓度分别为2 、3 、3 的三段此时得到的最⼤乘积是18。输⼊描述:输⼊⼀个数n意义⻅题⾯。2 n 60返回值描述:输出答案。示例1输⼊8返回值18思路及解答备忘录本题的解答思路就是每个⻓度的绳⼦要么最⻓的情况是不剪开⻓度是本身要么⻓度是剪开两段的乘积。因此每个⻓度 length 都需要遍历两个相加之后等于 length 的乘积取最⼤值。初始化值⻓度为 1 的值为 1 从⻓度为 2 开始每⼀种⻓度都需要遍历两个⼦⻓度的乘积。显然为了避免多次重复计算可以写个备忘录javapublic class Solution { public int cutRope(int target) { if (target 1) { return target; } int[] nums new int[target 1]; nums[1] 1; nums[0] 1; for (int i 2; i target; i) { int max i; for(int j0;ji/2;j){ int temp nums[j] * nums[i-j]; if(temp max){ max temp; } } nums[i]max; } return nums[target]; } }动态规划⽤动态规划的思维来做假设绳⼦⻓度为 n 的 最⼤的⻓度为 f(n) 那你说 f(n) 怎么计算得来呢f(n) 可能是 n(不切分)也可能是 f(n-1) 和 f(1) 的乘积也可能是 f(n-2) 和 f(2) 的乘积......那么也就是想要求 f( n ) 我们必须先把 f(n-1) f(n-2) ...之类的前⾯的值先求出来 f(1)1 这是初始化值。javapublic class Solution { public int cutRope(int target) { int[] dp new int[target 1]; dp[1] 1; for (int i 2; i target; i) { for (int j 1; j i; j) { dp[i] Math.max(dp[i], (Math.max(j, dp[j])) * (Math.max(i - j, dp[i - j]))); } } return dp[target]; } }时间复杂度O(n²)外层循环n-3次内层循环i/2次空间复杂度O(n)需要dp数组存储中间结果贪心算法最优解基于数学推导的贪心策略优先剪出长度为3的段。当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×1javapublic class Solution { 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次方 return (int)(Math.pow(3, countOf3)) * (int)(Math.pow(2, countOf2)); } }时间复杂度O(1)只有常数次操作空间复杂度O(1)只使用固定变量数学公式法理论最优根据n除以3的余数直接套用公式javapublic class Solution { public int cutRope(int n) { if (n 3) return n - 1; int countOf3 n / 3; int remainder n % 3; // 根据余数直接返回结果 if (remainder 0) { return (int) Math.pow(3, countOf3); } else if (remainder 1) { return (int) Math.pow(3, countOf3 - 1) * 4; } else { // remainder 2 return (int) Math.pow(3, countOf3) * 2; } } }