本文共 1266 字，大约阅读时间需要 4 分钟。

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

动态规划求解

我们定义函数$f(n)$为把长度为n的绳子剪成若干段后乘积的最大值

则$f(n)=max(f(i)-f(n-i))$：

• 把长度为n的绳子剪为长度为i和长度为n-i的两端，然后再求子问题$f(i)$和$f(n-i)$(i=1,2,...,n-1)

即：一个问题可以分解为子问题，要使得该问题最优，则子问题先要实现最优，因此我们可以使用动态规划的思路去求解

原问题从上到下使用递归法求解，动态规划的核心是填表，先求解子问题，然后自下而上求解，最终得到原问题的解

求解代码

class Solution {
   public:    int cutRope(int number) {
           if(number<4)return number;        else{
               int *tab =new int[number+1];//表格数组            int i,j;            //以下为填表过程            tab[0]=0;tab[1]=1;tab[2]=2;tab[3]=3;            for(i=4;i<=number;i++){
                   tab[i]=0;                for(j=1;j<=i/2;j++){
                       if(tab[i]

运行时间：3ms占用内存：608k

贪心法求解

尽可能地剪出长度为3的子段，但当最后一段所剩长度为4时，将其剪为2*2的两段落，因为2*2 > 3*1

PS：关于为何剪为3的子段的数学证明博主还没有想到如何用通俗易懂的方式讲解（可参考《剑指Offer》），欢迎大佬留言指教

求解代码

class Solution {
   public:    int cutRope(int number) {
           if(number<5)return number;        if(number%3==1)            return pow(3,number/3-1)*4;        else            return pow(3,number/3)*pow(2,(number%3)/2);    }};

运行时间：3ms占用内存：608k

转载地址：https://blog.csdn.net/Jeaten/article/details/108074146 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！