1. 剪绳子

  • 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 ``` 示例 1：

输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1 示例 2:

输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36 提示：

2 <= n <= 58

  1. <a name="4f7d0e2b"></a>
  2. #### 思路：
  3. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/12564843/1616159469826-876adf2a-b1ff-427e-965c-6ed038ce6093.png#align=left&display=inline&height=235&margin=%5Bobject%20Object%5D&name=image.png&originHeight=235&originWidth=844&size=12974&status=done&style=none&width=844)
  5. - 通过数学推导
  6.    - 根据“算数集合均值不等式”，进行推导，转换为最后所有分段的乘积的表达式，算出最大极大值对应驻点为x = e；
  7.    - 因此可以得到 ：
  8.       - 分成长度为3的多等分最优，2次之，1最差；
  9.       - 如果最后分出来有1，那么1对应的  1 * 3 < 2 * 2；因此将1和分出来的3转换为 2与2 是更优的。
  10. - 算法流程：
  11.    - n<=3时，最后结果为 n-1
  12.       - n=3，只能切分为2和1，最后结果为2
  13.       - n=2，只能切分为1和1，最后结果为1
  14.    - n>3时，尽量都分成长度为3的段；如果最后还剩一个1，那么将这个1与3变换成2和2
  15. ```java
  16. class Solution {
  17.     public int cuttingRope(int n) {
  18.         if(n<=3) return n-1;
  19.         int a = n/3, b = n%3;
  20.         if(b==0) return (int)Math.pow(3,a);
  21.         if(b==1) return (int)Math.pow(3,a-1)*4;
  22.         return (int)Math.pow(3,a)*2;
  23.     }
  24. }

  • 如果要在短时间内完成题目，数学推导就显得繁琐，这时使用贪心思想

  • 贪心思想：

    • 设一绳子长度为 n ( n>1 )，则其必可被切分为两段 n=_n_1+_n_2 。

    • 根据经验推测，切分的两个数成绩往往比原数要大，即往往 n1*n2 > n1 + n2 = n

      • 例如绳子长度为6：6 = 3 + 3<3*3 =9；
      • 也有少数特例3: 3= 2+1>2*1;

    • 推论： 合理的切分乘积大

      • 根据经验
      • 绳子往往切分段数多，则最后的乘积结果大。即：n = n1+n2+n3;n = n3 + n4;往往n1n2n3>n3*n4
        • 绳子长度为9: 4 5 < 3 3 * 3
        • 但也有少数情况，长度为6：3 3 > 2 2 * 2
      • 所以得出结论：合理的切分能够使乘积结果更大，不过大多数情况下还是越多越好

image.png

  • 根据推导，3不可再分，如果是1尽量和3结合成2与2

复杂度分析：

  • 时间复杂度 O(1) ： 仅有求整、求余、次方运算。
    • 求整和求余运算：资料提到不超过机器数的整数可以看作是 O(1) ；
    • 浮点取幂为 O(1)
  • 空间复杂度 O(1) ： 变量 a 和 b 使用常数大小额外空间。