每天一练（剑指offer）剪绳子

描述

给你一根长度为 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 。

示例

输入：

8

返回值：

18

说明：

8 = 2 +3 +3 , 2*3*3=18

思路????????

长度为1       最大值为1不切割

         2                     2不切割

         3                     3不

         4                     可2*2或者不切割

         5                     2*3，切割

         6                     3*3, 切割

         7                     3*4=3*2*2，切割

         8                     3*3*2，切割

由上????得

1 ????当其中的某一段的绳子，大于等于5的时候，就需要切割

2????当既存在大小为2的时候，又存在大小为4的时候，可合并为3（2*4<=3*3）而且，如果有2和4时，只能存其一

3????就令res=n/3（计算出3的n次方）,mod=n%3=0或1或2（当余数为0的时候，直接算出3的n次方）（当余数为1的时候，和其中的一个3合并起来）（当余数为2的时候3的n次方再乘2）

补充1：

为什么当x>=5的时候，切割或者不切割。

证明：我们切的话，定是切成二个尽量相等是，（x/2)(x/2)>x;当x>4时，该式子恒成立，所以x>=5时，切了收益更最大。而且需要把绳子切成2 3 4这种类型大小的时候它的乘积最大。                                                                                                                             

补充2：

有人可能会问，可以存在多个2吗？

证明：答案是不行的，比如存在3个2的话，我们可以把其中，两个2合成4，这个时候就会同时存在2和4了。多个4也是同样的道理，因为4也能分成2

代码如下????????

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 
* @param number int整型 
* @return int整型
*/
#include <math.h>
int cutRope(int number ) {
// write code here
if(number<=2)
    {
return 1;
    }
if(number==3)
    {
return 2;
    }
int res=number/3;
int mod=number%3;
if(mod==0)
    {
return pow(3,res);
    }
else if(mod==1)
    {
return pow(3,res-1)*4;
    }
else 
    {
return pow(3,res)*2;
    }
return res;
}

链接????????

​​​​https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8​​​

总结

????坚持每日????