[数据结构与算法]剑指offer_剪绳子（C++_动态规划/图解贪心算法）

原题链接

动态规划

1.思路

可以分析出来，因为题目要求必须剪。当绳子的长度小于2的时候不能剪了，这里返回0。当长度为2时只能1×1，乘积为1。当长度为3时最大乘积为1×2=2。

当长度>3时假设长度为n，在剪第一刀时有n-1种情况
假设一刀将绳子剪为i长与n-i长，乘积最大为F(n)=F(i)*F(n-i)
这个式子为一个递归式，其中有大量的重复计算。
所以我们从下往上开始记录，定义一个数组Cout，数组的下标值对应的是绳子的长度,下标对应的值为绳子在是下标长度时的最大乘积(最优解)。
所以F(n)=F(i)*F(n-i)可以写为max(Cout[i]*Cout[n-i])

2.动态规划C++代码

class Solution {
public:
    int cutRope(int number) {
        if(number<2)
            return 0;
        if(number==2)
            return 1;
        if(number==3)
            return 2;
        int* cout=new int[number+1];//多存放number=0情况
        cout[0]=0;
        cout[1]=1;
        cout[2]=2;
        cout[3]=3;
        for(int i=4;i<=number;i++)
        {
            int max=0;
            for(int j=1;j<=i/2;j++)//循环找最大乘积值
            {
                if(max<cout[j]*cout[i-j])
                {
                    max=cout[j]*cout[i-j];
                }
            }
            cout[i]=max;
        }
        return cout[number];
    }
};

3.代码注意

为什么当绳子长度<2时乘积为0，这里cout数组cout[0]=0,cout[1]=1

解：
能运行到cout数组这里说明其长度一定大于3
这里cout[1]=1不是说长度为1的绳子最大乘积为1，而是指如果剪后出现长度为1的绳子就不剪了。同理cout[3]表明当剪后出现长度为3的绳子就不剪了，如果再剪成1和2乘积为2<3就不是最优解了。
eg:长度为4的绳子先计算的为cout[1]×cout[3]相当于剪成了长度为1和长度为3的绳子对应数组下标的乘积值为1×3=3。

贪心算法

1.思路

同理：因为题目要求必须剪。当绳子的长度小于2的时候不能剪了，这里返回0。当长度为2时只能1×1，乘积为1。当长度为3时最大乘积为1×2=2。当绳子长度为4时最大乘积为2×2=4

当绳子长度>=5时

①证明一

我们发现当剪下的两条绳子长度的乘积大于等于其本身才有剪的意义
即i×(n-i)>=n（其中n>=5）

由上面可知我们要尽量选择剪出长度为2或者3的绳子，可以使最后的乘积最大，优先剪出长度为3的绳子。

②证明二

在绳子长度>=时5我们剪绳子最优解为：
一段长度为i与n-i的乘积要大于等于（i-1）与（n-i+1）同时还要大于等于(i+1)与(n-i-1)的乘积，即剪掉长度i是最优解

2.C++贪心算法代码

class Solution {
public:
    int cutRope(int number) {
        if(number<2)
            return 0;
        if(number==2)
            return 1;
        if(number==3)
            return 2;
        int CoutPow3=number/3;//计算可以切出几个长度为3的绳子
        if(number-3*CoutPow3==1)
    //如果切到最后长度为4，单独处理长度为4的绳子，切成2*2，最大乘积为4
        {
            CoutPow3--;
            return pow(3,CoutPow3)*4;
        }
        if(number-3*CoutPow3==2)
     //切到最后长度为2，这时不需要再切了长度为2
        {
            return pow(3,CoutPow3)*2;
        }
     //正好可以切成整数个长度为3的绳子
        return pow(3,CoutPow3);
    }
};