题目描述

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

https://leetcode.cn/problems/jian-sheng-zi-lcof/
https://leetcode-cn.com/problems/integer-break/

题解

动态规划

dp[i]：将正整数 i 拆成至少两个正整数的和之后，这些正整数的最大乘积。
特别的，0 不是正整数，1 是最小的正整数，都不能拆分，因此 dp[0] = dp[1] = 0 。

当 i >= 2 时，假设对正整数 i 拆分出的第一个正整数是 j (1 <= j < i)，则有以下两种方案：

将 i 拆分成 j 和 i - j 的和，且 i - j 不再拆分成多个正整数，此时的乘积是 j * (i - j)
将 i 拆分成 j 和 i - j 的和，且 i - j 继续拆分成多个正整数，此时的乘积是 j * dp[i - j]

因此，当 j 固定时，有 dp[i] = max(j * (i - j), j * dp[i - j])，而 1 <= j < i，遍历所有的 j 得到 dp[i] 的最大值。

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

时间复杂度 $O(n^2)$
空间复杂度 $O(n)$

动态规划：时间优化（剪枝）

上述 1 <= j < i，可以证明 i >= 3 时只需考虑 j = 2 或 j = 3 时的情况即可。
而 i = 2 时是边界情况，唯一的拆分方案是 2 = 1 + 1，最大乘积是 1 * 1 = 1 。
证明过程

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n + 1, 0);
        dp[2] = 1;                      // dp[0] = dp[1] = 0
        for (int i = 3; i <= n; ++i) {
            dp[i] = max(max(2 * (i - 2), 2 * dp[i - 2]), max(3 * (i - 3), 3 * dp[i - 3]));
        }
        return dp[n];
    }
};

时间复杂度 $O(n)$
空间复杂度 $O(n)$

数学

每个大于 4 的数 x 一定可以拆分成两个数使乘积大于 x 。
所以如果拆分结果中存在大于等于 4 的数，一定需要被再次拆分，最终都会被拆分成尽可能多的 3，或有一个 2 。
证明过程
题外话：类似的，有多边形边越趋于相等总面积越大，即周长相等时圆的面积最大。

// 总之是将给定的正整数拆分成尽可能多的 3，不能整除 3 就拆出来 2
// 特殊情况当 n <= 3 时，刚好最大乘积是 n - 1
class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int quotient = n / 3, remainder = n % 3;
        switch(remainder) {
            case 0: return (int)pow(3, quotient);
            case 1: return (int)pow(3, quotient - 1) * 4;
            case 2: return (int)pow(3, quotient) * 2;
        }
        return -1;
    }
};