class Solution {
public:
    //递归
    //递归终止条件：剩余绳子长度
    //传递值：当前段、剩余段的大小，乘积
    //递推工作：每一段从1开始尝试到末尾
    int maxnum=1;
    void dfs(int start,int temp,int n){
        if(n==1||n==0){
            maxnum=max(maxnum,temp);
        }
        //cout<<start<<" "<<temp<<" "<<n<<endl;
        for(int i=0;i<n-1;i++){
            dfs(start+i,temp*(start+i),n-start-i);
        }
    }
    int cuttingRope(int n) {
        dfs(1,1,n);
        return maxnum;
    }
};

后面两种方法参考：
剑指 Offer 14- I. 剪绳子，还是动态规划好理解，但是贪心真的快

2.动规（看题解的方法，也是一开始没想出来的最适合本题的方法,n<=120）

核心：递归方程式

class Solution {
public:
    //动规
    //dp[i]表示长度为i的绳子减去m段后的最大乘积。
    //状态转移方程式：剩下的一段可以剪掉，也可以不减掉，取最大值
    int cuttingRope(int n) {
        vector<int> dp(n+1,1);
        for(int i=3;i<=n;i++){
            for(int j=2;j<i;j++){
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    int MOD=1000000007;
    int cuttingRope(int n) {
        if(n<4){
            return n-1;
        }
        long int sum=1;
        while(n>4){
            sum*=3;
            sum%=MOD;
            n-=3;
        }
        return (int)(((long)(sum*n))%MOD);;
    }
};