題目描述
- 給定一根長度為n的繩子坑律，請把繩子剪成m段（m体箕、n都是整數(shù)痕钢，n>1并且m>1），每段繩子的長度記為k[0],k[1],…,k[m]鱼冀。請問k[0]* k[1] * … *k[m]可能的最大乘積是多少？
- 例如悠就，當(dāng)繩子的長度是8時(shí)千绪，我們把它剪成長度分別為2、3梗脾、3的三段荸型，此時(shí)得到的最大乘積是18
題目解讀
- 劍指Offer 96
代碼
- 思路一、動(dòng)態(tài)規(guī)劃
#include<iostream>
using namespace std;
int maxProductAfterCutting_solution1(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;
}
int main(){
// cout<<maxProductAfterCutting_solution1(3)<<endl; // 2
cout<<maxProductAfterCutting_solution1(8)<<endl; // 18
}
思路二炸茧、貪婪算法
#include<iostream>
#include<math.h>
using namespace std;
int maxProductAfterCutting_solution1(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 的時(shí)候瑞妇，不用再減去長度為 3 的繩子段
// 此時(shí)更好的方法是把繩子剪成長度為 2 的兩段稿静，因?yàn)?2x2 > 3x1
if(length - timesOF3/3 == 1){
timesOF3 -= 1;
}
int timesOF2 = (length - timesOF3 * 3) / 2;
return (int)(pow(3, timesOF3)) * (int)(pow(2, timesOF2));
}
int main(){
// cout<<maxProductAfterCutting_solution1(3)<<endl; // 2
cout<<maxProductAfterCutting_solution1(8)<<endl; // 18
}
總結(jié)展望
- 對于動(dòng)態(tài)規(guī)劃和貪婪算法不熟悉，等做完劍指Offer辕狰，去LeetCode 多做幾道.
