题目描述

  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。
  3. 示例 1：
  5. 输入: 2
  6. 输出: 1
  7. 解释: 2 = 1 + 1, 1 × 1 = 1
  8. 示例 2:
  10. 输入: 10
  11. 输出: 36
  12. 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
  13. 提示：
  15. 2 <= n <= 58

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

这种题目应该用什么思路去解决呢？
因为这种题目本身场景很特殊，需要找到一定的规律，所以我感觉就是你能不能准确把握到这个规律，然后让程序准确的复现你的规律判断规则。

那么这一题的规律是什么呢？

首先是我想分段的话我肯定不想分1，因为分1是无意义消耗绳子长度，对绳子长度低效利用的体现
但是，有的时候会不得不分为1，比如长度为3，分成两段，必须是1+2

然后，在绳子长度可以不分为1的情况下，各个分段的长度，尽可能的靠近，10 = 3+3+4 或者4+4+2
但是很明显，334的分布比442更接近 ，但是2 2 2 2 2这种呢？32还是小，所以分成2比分成1好，分成3比分成2好，3331<3322 ，所以我们可以发现这种规律，优先分成3，其次是2，尽量避免1。

那么怎么用算法逻辑来表示这种规律呢？
这种就可以利用类似背包问题中的贪心思想，因为3 的优先级大于2大于1，优先满足3，但是要考虑避免出现1 。

代码

  1. class Solution {
  2. public:
  3.     int cuttingRope(int n) {
  4.         int ans=1;
  5.         int total = 0;
  6.         int a=3,b=2,c=1;
  7.         if(n<=2){
  8.             return 1;
  9.         }
  10.         if(n==3) return 2;
  11.         while(total+a<=n-2){
  12.             ans*=a;
  13.             total+=a;
  14.         }
  15.         if(total+a==n){
  16.             ans*=a;
  17.             return ans;
  18.         }
  19.         while(total+b<=n){
  20.             ans*=b;
  21.             total+=b;
  22.         }
  23.         return ans;
  25.     }
  26. };

复杂度分析

O(n)
因为是循环的用3和2来分割输入n