• 题目难度：中等

  • 题目描述：

    给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。
  • 数据范围： 2 ≤ n ≤ 60
  • 进阶：空间复杂度 O(1) ，时间复杂度 O(n)

  • 示例1:

    输入：8
    返回值：18
    说明：8 = 2 +3 +3 , 2*3*3=18

  • 思路1：强行数学解释：

    时间复杂度：O(1)
    运行时间：3ms 占用内存：584KB
    借用一下某位 博主 的图
    图片说明 

    class Solution {
public:
  int cutRope(int number) {
      if(n <= 2) return 1;
      if(n == 3) return 2;

      int n =  number;
      int m = n % 3;
      if (m == 0) return (int)pow(3, n / 3);
      else if (m == 1) return (int)pow(3, n / 3 - 1) * 4;
      else return (int)pow(3, n / 3) * 2;
  }
}

  • 思路二：动态规划：

    时间复杂度：O()
    运行时间：3ms 占用内存：428KB
    动态规划问题主要思路：

    • 状态表示：怎么去表示问题的状态

      • 此问题：dp[i] 表示长度 i 时，可达到的最大乘积

    • 状态计算：怎么计算当前状态
      图片说明 

      class Solution {
private:
int dp[70];
public:
int cutRope(int number) {
  if(number <= 3) return number - 1;
  memset(dp, 0, sizeof dp);
  dp[1] = 1, dp[2] = 2, dp[3] = 3, dp[4] = 4;

  for(int i = 5; i <= numbers; ++i)
      for(int j = 1; j <= i / 2; ++j) 
          dp[i] = max(dp[i], dp[i - j] * j);
  }
}

  • 思路三：贪心算法(推荐)

    运行时间：3ms 占用内存：524KB
    时间复杂度：O(n)，空间复杂度：O(1)
    使用贪心思想，不断将绳子分成每段长度为 3 即可让乘积达到最大

    class Solution {
public:
  int cutRope(int number) {
      if(number <= 3) return number - 1;
      int res = 1; 
      while (number > 4) {
          res *= 3;
          number -= 3;
      }
      return res * number;
  }
}

    😘😘😘😘😘😘😘😘😘😘😘