剑指offer-67、剪绳⼦
题目描述
给你⼀根⻓度为n 的绳⼦，请把绳⼦剪成整数⻓的m 段（ m 、n 都是整数， n>1 并 且m>1 ， m<=n ），每段绳⼦的⻓度记为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 开始，每⼀种⻓度都需要遍历两个⼦⻓度的乘积。
显然，为了避免多次重复计算，可以写个备忘录
java
public 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 j=0;j<=i/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 这是初始化值。
java
public 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.718，3是最接近的整数
- 4的特殊处理：2×2 > 3×1，所以剩余4时剪成2×2而不是3×1
java
public 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的余数直接套用公式
java
public 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; } } }