offer_14

//动态规划和贪婪算法；面试题14：剪绳子

//方法1：动态规划
int maxProductAfterCutting_solution(int length)
{
  if(length<2) return 0;
  if(length==2) return 1;
  if(length==3) return 2;
  int* products=new int[length+1];
  products[0]=0;
  products[1]=1;
  products[2]=2;
  products[3]=3;

  for(int i=4;i<length;++i){
    max=0;
    for(int j=1;j<=i/2;++j){
      int product=products[j]*products[i-j];
      if(max<product)
        max=product;
        
       products[i]=max;
    }
  }
  max=products[length];
  delete[] products;
  return max;
}



//方法2：贪婪算法
int maxProductAfterCutting_solution2(int length)
{
  if(length<2) return 0;
  if(length==2) return 1;
  if(length==3) return 2;
  int timesOf3=length/3;//尽可能多的剪去长度为3的绳子段
  //当绳子最后剩余的长度为4时，不能再剪去长度为3的绳子段，此时更好的办法是将绳子剪成长度为2的两段，因为2*2>3*1
  int (length-timesOf3*3==1)
    timesOf3-=1;
   int timesOf2=(length-timesOf3*3)/2;
   return (int)(pow(3,timesOf3))*(int)(pow(2,timesOf2));
}