📃 题目描述

题目链接：

🔔 解题思路

和这题 剑指 Offer 14- I. 剪绳子 (opens new window) 的唯一不同就是，这里的 n 范围变大了，如果用 dp 来做，会出现大数越界情况，对每次的dp[i] 取余确实可以避免溢出的问题，但是由于过程中修改了值，会导致最终结果和预期不同，比如 dp[i] = Math.max(dp[i] ，x * y ); x * y = 1000000005 ，若dp[i] 本该等于 1000000008 ，但是经过上次取余后变成了1，本来的结果应该是1000000008 ，现在却变成了1000000005，所以在动态规划过程中是不能取余的。可以使用 BigInter 来存储结果，把 dp 数组类型改成 BigInteger 就行，这里就不写了。

我们这里想给出的算法思想是贪心：

• 当绳子长度大于4时，尽可能多的分成长度为3的小段，这样乘积是最大的（数学证明自行查找）

思路：

• n 小于 4 时，返回 n-1
• n 等于 4 时，返回 4
• n 大于 4 时，就要切割成长度为 3 的小段，只要 n 还大于 4，每切除一段 3，就累乘起来，然后取模

class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        else if (n == 4) {
            // 2x2 > 3x1
            return 4;
        }
		
        long res = 1;
        // n > 4
        while (n > 4) {
            res = (res * 3) % 1000000007;
            n -= 3;
        }

        // n == 4, 拆成 2*2 = 4
        return (int)((res * n) % 1000000007);

    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：