动态规划解决

class Solution {
public:
    int cutRope(int number) {
        //选取剪绳子的第一段的长度，计算出其最大乘积长度，然后乘以剩余一段的最大乘积长度
        //以选出最终的最大乘积长度，每一分割绳子段都是先前过程中计算出来的
        //由于已知n>0,m>0,则可以知道绳子必须进行分割，然后建立辅助vector，注意下标的关系
        //当number<2时，并不满足题意，返回0
        if (number < 2)
            return 0;
        //当number==2时，
        else if(number==2)
            return 1;
        else if(number == 3)
            return 2;
        //当number>=4的时候
        //则要进行辅助空间的定义
        vector<int> dp(number+1,0);
        dp[0] = 0;
        dp[1] = 1;//剪绳子的第一段都是从1开始的
        dp[2] = 2;//代表第一段绳子长度为2，而并不是上面进行返回的最大乘积
        dp[3] = 3;//代表第一段绳子长度为3，而不是上面进行返回的最大乘积
        for(int i=4;i<=number;i++){
            int max=0;
            //限制条件为j<=number/2的原因为：如果第一段选取的绳子的长度大于了number的一半
            //则将会与先前进行分割的情况重复
            for(int j=1;j<=number/2;j++){
                max=dp[j]*dp[i-j]>max?dp[j]*dp[i-j]:max;
            }
            dp[i]=max;
        }
        return dp[number];
    }
};