题目描述

• 给定一根长度为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 多做几道.

参考

• 剑指Offer-14：剪绳子