題目：給你一根長度為n的繩子肠骆，請把繩子剪成m段（m、n都是整數(shù)，n>1并且m>1）冬耿，每段繩子的長度記為k[0],k[1],···,k[m]。請問k[0]×k[1]×···×k[m]可能的最大乘積是多少萌壳？例如亦镶，當(dāng)繩子的長度是8時，我們把它剪成長度分別為2袱瓮、3缤骨、3的三段，此時得到的最大乘積是18尺借。
練習(xí)地址
https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
方法1：動態(tài)規(guī)劃
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[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;
}
return products[length];
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n^2)绊起。
- 空間復(fù)雜度：O(n)。
方法2：貪婪算法
public int maxProductAfterCutting(int length) {
if (length < 2) {
return 0;
}
if (length == 2) {
return 1;
}
if (length == 3) {
return 2;
}
// 盡可能多地剪去長度為3的繩子段
int timesOf3 = length / 3;
// 當(dāng)繩子最后剩下的長度為4的時候燎斩，不能再剪去長度為3的繩子段
// 此時更好的方法是把繩子剪成長度為2的兩段虱歪，因為2x2>3x1
if (length - timesOf3 * 3 == 1) {
timesOf3 -= 1;
}
int timesOf2 = (length - timesOf3 * 3) / 2;
return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
}
復(fù)雜度分析
- 時間復(fù)雜度：O(1)蜂绎。
- 空間復(fù)雜度：O(1)。
