题目
给你一根长度为n的绳子，请把绳子剪成m段(m,n都是整数，n>1且m>1)。每段绳子的长度记为k[0],k[1],.....,k[m]。请问k[0]k[1]....*k[m]可能的最大乘积是多少?
举例:当绳子的长度是8时，先把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18.
解题思路
- 动态规划
尝试把大问题分解成小问题，分解后的每个小问题也存在最优解。如果把小问题的最优解组合起来能够得到整个问题的最优解，那么可以应用动态规划解决这个问题。
- 把长度为n的绳子剪成若干段后得到的乘积最大值定义为函数f(n)。假设第一刀剪在长度为i(0<i<n)的位置，于是绳子剪成长度分别为i和n-i的两段。要想得到整个问题的最优解f(n)，那么要同样用最优化的方法把长度为i和n-i的两段分别剪成若干段。
- 采用从下往上的顺序计算小问题的最优解并存储下来，再依次为基础求取大问题的最优解。
- 贪婪算法
应用贪婪算法解决问题时，每一步都可以做出一个贪婪选择，基于这个选择，确定能够得到最优解。
当绳子的长度大于5时，每次都剪出一段长度为3的绳子。
代码
- 动态规划
- 细节
自上而下分析问题，自下而上解决问题。
- 先计算前三个小问题的最优解并存储在products数组中
- 从长度为4的绳子开始分析每一种可能性，并取最大值。
class Solution{
public:
int maxProductAfterCutting(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;
int max;
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;
}
};
- 贪婪算法
class Solution{
public:
int maxProductAfterCutting2(int length)
{
if(length < 2) return 0;
if(length == 2) return 1;
if(length == 3) return 2;
//尽可能多地减去长度为3的绳子
int timesOf3 = length / 3;
//若绳子最后剩下的长度为4时，不用再减去长度为3的绳子段
//此时更好的方法是把绳子剪成长度为2的两段，因为2*2 > 3*1
if(length - timesOf3/3 == 1)
{
timesOf3 -= 1;
}
int timesOf2 = (length - timesOf3 * 3) / 2;
return (int)(pow(3,timesOf3))*(int)(pow(2,timesOf2));
}
};
