题目描述：

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

题解:动态规划(题解来自Maokt)

1. 我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而
2. 用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
3. 我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
4. 剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
5. 第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])) 6、最后返回dp[n]即可

图示(来自leaves0924)

代码

class Solution {
public:
    int cutRope(int number) {
        //动态规划
        vector<int> dp(number+1,0);
        dp[2] = 1;//长度为2的绳子的最大积
        for(int i =3;i<number+1;i++){
            for(int j =2;j<i;j++){//每次从段长为2开始剪
                dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[number];
    }
};

题解2：贪心算法

算法思路：尽可能多地分为段长为3的部分

1. 当 n≤3 时，按照规则应不切分，但由于题目要求必须剪成 m>1 段，因此必须剪出一段长度为 1 的绳子，即返回 n−1 。
2. 当 n>3 时，求 n 除以 3 的 整数部分 a 和 余数部分 b （即 n=3a+b ），并分为以下三种情况：
   当 b = 0 时，直接返回 3^a；
   当 b = 1 时，要将一个 1+3 转换为 2+2，因此返回 3^(a-1) x 4；
   当 b = 2 时，返回 3^a ×2。

代码

class Solution {
public:
    int cutRope(int number) {
        if (number == 2)
            return 1;
        if (number == 3)
            return 2;
        int t3 = number / 3;//number中能够分为长度为3的个数
        if ((number - 3 * t3) == 0)
            return pow(3, t3);//如果3的个数为整数,pow是求幂函数
        if ((number - 3 * t3) == 1)
        {
            t3 = t3 - 1;
            return 4 * pow(3, t3);
        }
        if ((number - 3 * t3) == 2) {
            return 2 * pow(3, t3);
        }
        return 0;
    }
};