题目
给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。
每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？
例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
样例
输入：8
输出：18

解法一：动态规划

动态规划应该是做这道题的第一想法
f[n] = f[i] * f[j - i]
自底向上求出f[i]即可
注意题目要求至少切成两段，因此f[2],f[3]需要特判
时间复杂度O(n^2)，空间复杂度O(1)

class Solution {
public:
    int f[60];
    int maxProductAfterCutting(int length) {
        if (length == 2) return 1;
        else if (length == 3) return 2;
        f[1] = 1, f[2] = 2, f[3] = 3;
        for (int i = 4; i <= length; i++) {
            for (int j = 1; j <= i / 2; j++) {    // j 枚举到 i / 2 即可
                f[i] = max(f[i], f[j] * f[i - j]);
            }
        }
        return f[length];
    }
};

解法二：贪心

尽可能将绳子剪成长度为2，3
n = 2, 3时仍需特判
证明如下：

1. 显然不会切出1
2. n>=5时，将n拆分成3+(n-3)，有3(n-3) > n
3. 如果n=4，拆成2+2乘积不变
4. 如果有三个以上2，222<3*3

所以尽可能使用3，余1时凑一个4，余2时切出一个2

class Solution {
public:
    int maxProductAfterCutting(int length) {
        if (length <= 3) return length - 1;
        int res = 1;
        if (length % 3 == 1) {
            res *= 4;
            length -= 4;
        }
        else if (length % 3 == 2) {
            res *= 2;
            length -= 2;
        }
        while (length) {
            res *= 3;
            length -= 3;
        }
        return res;
    }
};