题目

给你一根长度为 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。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解答

基本思路与剑指Offer I 14- I. 剪绳子一致，但此题需要解决大数求余问题。

此外，因为要取模 1e9+7，会影响最大值的判断，所以本题不能直接用dp方法求解。

所以采用贪心的思路，加上快速幂求余的技巧。

方法一：动态规划

也可以用，不过要么用两个值记录状态，要么用 py 或者 Java 的 bigint 。

方法二：贪心+快速幂

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    typedef long long ll;
    ll qPow(ll a, ll e, int mod) { // 带求余的快速幂
        ll res = 1;
        while (e) {
            if (e&1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            e >>= 1;
        }
        return res;
    }

    int cuttingRope(int n) {
        const int mod = 1000000007;
        if(n < 4) return n - 1;
        int rem = n % 3;
        ll tmp = qPow(3, n/3-1, mod); // n除3向下取整-1，先保留一个3
        if (rem == 0) { // mod 3 == 0，*3
            return tmp * 3 % mod;
        } else if (rem == 1) { // mod 3 == 1，用保留的3和这个1恢复成4再分成2、2，2*2 > 3*1
            return tmp * 4 % mod;
        } else { // mod 3 == 2，不能再分，*2*3
            return tmp * 6 % mod;
        }
    }
};

复杂度

  • 时间复杂度 O(log N)：快速幂二分法为对数级别复杂度。
  • 空间复杂度 O(1)