题目描述：

给定一根长度为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。

动态规划：（剑指offe版）

• 定义函数f(n)表示为把长度为n的绳子剪成若干段后各段长度乘积的最大值。
• 在剪第一刀的时候，我们有n-1种可能的选择，可推导出f(n)=max{f(i)*f(n-i)}（0<i<n）;
• 这是一个从上至下的递归，但是这个递归存在很多重复的计算，所以使用至下而上的动态规划，将子问题的最优解保存。
• 注意绳子剪成ix(n-i)和(n-i)xi是相同的；
• 注意不符合切割条件的输入n，以及输入为2、3长度时的结果，因为题中规定m>1。(边界条件、及非法输入）

int maxMulti(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]=1;
    products[1]=1;
    products[2]=2;
    products[3]=3;
    
    int max=0;
    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;
}

在上述问题中，子问题的最优解存储在数组products里。数组第i个元素表示把长度为i的绳子剪成若干段长度乘积的最大值，即f（i）。我们注意到代码中第一个for循环变量i是循序递增的，这意味着计算是自下而上的。因此在求f（i）之前，对于每一个j（0<i<j）而言，f（j）都已经求解出来了，并且结果都存在projects[j]里。为了求解f(i)，我们需要求出所有可能的f(j)xf(i-j)并比较得出它们的最大值。这就是代码中第二个循环的功能

贪婪算法

如果我们按照如下的策略来剪绳子，则得到的各段绳子的长度的乘积将最大：当n>=5时，我们尽可能多地剪长度为3的绳子;当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子。这种思路对应的代码如下：

      证明：首先，当n>=5的时候，我们可以证明2（n-2）>n并且3（n-3）>n,也就是说，当绳子剩下的长度大于或等于5的时候，我们就把它剪成长度为3或者2的绳子段。另外，当n>=5时，3（n-3）>=2（n-2）,因此我们应该尽可能地多剪长度为3的绳子段。

     前面的证明的前提是n>=5。那么当绳子的长度为4呢？在长度为4的绳子上剪一刀，有两种可能的结果：剪成长度分别为1和3的两根绳子，或者两根长度都为2的绳子。注意到2x2>1x3，同时2x2=4，也就是说，当绳子长度为4时其实没有必要剪，只是题目至少要求一刀

首先应该注意到的是我们无论剪成什么样都可以分解成质数相乘的情况（这里把1囊括进来了），于是可以得到最基础的几个质因数：2,3；

int maxMulti(int length){
    if(length<2)
        return 0;
    if(length==2)
        return 1;
    if(length==3)
        return2;
    int timesOf3=length/3;
    if(length-timesOf3*3==1)
        timesOf3-=1;
    int timesOf2=(length-timesOf3*3)/2;
    return(int)(pow(3,timesOf3))*(int)(pow(2,timesOf22));
}

内容来源:《剑指offer》