题目描述
- 给定一根长度为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
题目解读
- 剑指Offer 96
代码
- 思路一、动态规划
#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;
// 当绳子最后剩下的长度为 4 的时候，不用再减去长度为 3 的绳子段
// 此时更好的方法是把绳子剪成长度为 2 的两段，因为 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
}
总结展望
- 对于动态规划和贪婪算法不熟悉，等做完剑指Offer，去LeetCode 多做几道.
