给你一根长度为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
。
时间复杂度O(n²)
,空间复杂度O(n)
。
/**
* @author bingo
* @since 2018/11/20
*/
public class Solution {
/**
* 剪绳子求最大乘积
* @param length 绳子长度
* @return 乘积最大值
*/
public int maxProductAfterCutting(int length) {
if (length < 2) {
return 0;
}
if (length < 4) {
return length - 1;
}
// res[i] 表示当长度为i时的最大乘积
int[] res = new int[length + 1];
res[1] = 1;
res[2] = 2;
res[3] = 3;
// 从长度为4开始计算
for (int i = 4; i <= length; ++i) {
int max = 0;
for (int j = 1; j <= i / 2; ++j) {
max = Math.max(max, res[j] * res[i - j]);
}
res[i] = max;
}
return res[length];
}
}
时间复杂度O(1)
,空间复杂度O(1)
。
贪心策略:
证明:
/**
* @author bingo
* @since 2018/11/20
*/
public class Solution {
/**
* 剪绳子求最大乘积
* @param length 绳子长度
* @return 乘积最大值
*/
public int maxProductAfterCutting(int length) {
if (length < 2) {
return 0;
}
if (length < 4) {
return length - 1;
}
int timesOf3 = length / 3;
if (length % 3 == 1) {
--timesOf3;
}
int timesOf2 = (length - timesOf3 * 3) >> 1;
return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
}
}