剪绳子
剪绳子
http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8
这道题可以用两个方法解决:
1、动态规划
分析：当绳子长度为n时，将它剪成若干段后各长度乘积有一个最大值f(n)，假设剪下第一刀，则绳子分为长度为i和长度为n-i的两段，所以f(n)=max(f(i)*f(n-i)),易知这是一个从上至下的递归公式，
但是递归从上至下计算繁琐，而我们很容易得出f(0)、f(1)、f(2)、f(3)的值，所以我们可以采取从下至上的方式：
int cutRope(int number) {
if(number<2)
return 0;
if(number==2)
return 1;
if(number==3)
return 2;
int *products=new int[number+1]; //存储子问题最优解
products[0]=0;
products[1]=1;
products[2]=2;
products[3]=3;
int max=0;
for(int i=4;i<=number;++i)
{anzhaoruxiacelue
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[number];
delete []products;
return max;
} 2、贪婪算法 按照如下策略剪绳子，则得到的各段绳子的长度的乘积将最大；当n>=5时，我们尽可能多的剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2 的绳子：
至于为什么是3就要用数学方法去证明了，有兴趣可以搜索相关资料证明。
int cutRope(int number) {
if(number==0)
return 0;
if(number==2)
return 1;
if(number==3)
return 3;
int max=0;
int timesOf3=number/3;
if(number-timesOf3*3==1)
{
timesOf3-=1;
max=(int)(pow(3,timesOf3))*4;
}
else if(number-timesOf3*3==2)
max=(int)(pow(3,timesOf3))*2;
else max=(int)(pow(3,timesOf3));
return max;
} 
查看10道真题和解析
