题目
给你一根长度为 n 的绳子,请把绳子剪成 m 段(m、n 都是整数,n>1 并且 m >1),每段绳子的长度记为 k[0],k[1],…,k[m]。请问 k[0]xk[1]x…xk[m]可能的最大乘积是多少?例如,当绳子的长度是 8 时,我们把它剪成长度分别为 2、3、3 的三段,此时得到的最大乘积是 18。
输入描述
输入一个数 n,意义见题面。(2 <= n <= 60)
输出描述:
输出答案。
解题思路
1 动态规划
- 条件一:求一个问题的最优解
- 条件二:该问题能够分解成若干个子问题,并且子问题也存在最优解
- 条件三:子问题之间还有重叠的更小的子问题
2 本题思路
- 求剪出绳子长度的乘积的最大值,这个符合第一个条件
- 我们将乘积以函数表示,即 f(n)。假设第一刀减在长度为 i(0<i<n)的位置,于是把绳子剪成了长度分别为 i 和 n - i 两段。想要得到整个问题的最优解 f(n), 就需要同样用最优化的方法把长度为 i 和 n - i 的两段分别剪成若干段,使得它们剪出的每段绳子的长度成绩最大。这符合第二个条件。
- 大问题分解为小问题时,会出现相互重叠的更小的子问题。如,绳子长为 10,首先将其分为 4 和 6。长度为 4 的一段,可以分为 2 和 2;长度为 6 的可以分为 2 和 4。可以发现,f(2)是 f(4)和 f(6)公共的更小的子问题。
所以,这里采取的方法是自下而上的方法。先从小问题开始计算,并把已经解决的子问题的 最优解存储 下来(通常的做法是存储在一位数组或者二维数组中),并把子问题的最优解组合起来逐步解决大的问题。
3 测试用例
- 功能测试用例:绳子的长度大于 5
- 边界测试用例:绳子的长度分别为 0,1,2,3,4
/**
* 使用动态规划的方法
* @param length
* @return
*/
public static int getMaxResult(int length) {
// 如果 length 小于等于 3,则直接输出结果
if (length < 2)
return 1;
if (length ==2)
return 1;
if (length == 3)
return 2;
// 如果 length 大于 3,则又有新的内容
int[] results = new int[length + 1];
// 这里说明下,现在 length 大于 4,那么当子问题分别为 0,1,2,3 时,我们直接不分不切割,此时就是子问题对应的最优解
results[0] = 0;
results[1] = 1;
results[2] = 2;
results[3] = 3;
int max = 0;
for (int i = 4; i <= length; i++) {max = 0;// 每次都有重置最大值,因为有可能上次求出的分段内容最大值大于 f(j)*f(j-1)的值,最终得到的很有可能是上次的最大值
for (int j = 1; j <= i / 2; ++j) {int result = results[j] * results[i-j];
if (max < result) {max = result;}
results[i] = max;
}
}
max = results[length];
return max;
}
4 尝试贪婪算法
分为下面几种情况:
- n<2, 返回 0
- n==2, 最大乘积为 1
- n==3, 最大乘积为 2
- n==4, 最大乘积为 2 *2=4
- n>=5, 需要进行以下说明
当 n >= 5 时,我们可以分别切割为 1 (n-1)、2(n-2)、3(n-3)、4(n-4)、5*(n-5)
得到的时 3 (n-3)得到的结果最大,紧跟着的是 2 (n-2)。所以应该尽可能多的将绳子切割为 3。
此时,会出现剩余为 1 或 2 两种情况。如果为 1 的话,我们需要将剩余的长度修改为 4,因为 4 (n-4)>1(n-1);如果剩余为 2 的话,没有办法再切割了。
所以,其中算法的思路是:
- 向下取整,求 3 的倍数
- 如果剩余的长度为 1,可将 3 的倍数减一(使剩余的内容为 4)
- (总长度 -3* 3 的倍数)/2 的到 2 的倍数
- 最终的结果是 pow(3,3 的倍数)*pow(2,2 的倍数)
/**
* 使用贪婪算法
* @param length
* @return
*/
public static int getMaxResult2(int length) {
// 如果 length 小于等于 3,则直接输出结果
if (length < 2)
return 1;
if (length ==2)
return 1;
if (length == 3)
return 2;
// 求出可以切割成 3 的个数
int timesof3 = length / 3;
// 当以 3 为单位来切割时,如果最后一段的长度为 4,需求将最后一段按照 2 + 2 来切割
if (length - timesof3 * 3 == 1) {timesof3--;}
// 求出可以剩余可以切割为 2 的个数
int timesof2 = (length - timesof3 * 3) / 2;
return (int)(pow(3, timesof3)) * (int)(pow(2, timesof2));
}
本题 github 地址,欢迎 star
https://github.com/justn0w/algorithm/tree/master/offer_16