题解 | #剪绳子#

剪绳子：最直观的想法是，长度为n的绳子分为m段，由于绳子长度越接近乘积越大，那么每一段长度为n/m，假设乘积为y，则y=(n/m)^m，两边进行取对数，则lny=mln(n/m)，两边对m进行求导，则可得y'1/y=ln(n/m)+mm/n(-n/m²)，即y'=(ln(n/m)-1)(n/m)^m，令y'=0，则m=n/e，故绳子长度为n/m=e，e约等于2.7，又绳子长度为整数，故取3最大。由于将绳子长度分为1时，只会减少长度，而不会增加乘积，又m>1，故n=2时分为1和1结果为1，n=3时分为2和1结果为2，当n>=4时，如果n%3==0，则结果为3的n/3次方，如果n%3==1，则结果为划分一个4出来，如果n%3==2，则结果为划分一个2出来。

int cutRope(int number) 
{
   if(number==2||number==3)
      return number-1;
   if(number%3==0)
      return (int)pow(3,number/3);
   if(number%3==1)
      return 4*(int)pow(3,(number-4)/3);
   return 2*(int)pow(3,number/3);
}

idea：长度为i的绳子，可以将其分为两部分，一部分是j，另一部分是i-j，如果要i分的最大，那么就需要j和i-j均分的最大，其中j只需要循环到i/2即可，此时我们可以设置一个dp数组，其中dp[i]表示长度为i的绳子可以分得的最大值，此时dp[1]=1,dp[2]=2,dp[3]=3,这三个表示的是不分的最大值，注意这一点不要和长度为2和3的绳子返回1和2进行混淆，那么递推公式即为dp[i]=max(dp[i],dp[j]*dp[i-j])，最终的结果即为dp[number]。如果不是很懂，可以画一个数组来进行代码模拟，从而帮助理解。

int cutRope(int number) 
{
   if(number==2||number==3)
      return number-1;
   vector<int> dp(number+1);
   dp[1]=1;
   dp[2]=2; //当i<4时 dp[i]存储的是不分割的最大值
   dp[3]=3;
   for(int i=4;i<=number;i++)
   {
      for(int j=1;j<=i/2;j++) //计算一半即可 后面一半与前面一半相当于重复 将i分成j和i-j
      {
          dp[i]=max(dp[i],dp[j]*dp[i-j]);
      }
   }
   return dp[number];
}