题解 | #剪绳子（进阶版）#

题目的主要信息：

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

方法一：

暴力法。根据均值不等式： 当$a_1=a_2=\mathrm{.}\mathrm{.}\mathrm{.}=a_{n}a\_1=a\_2=...=a\_n$时等号成立，所以此题要使乘积最大，应该把绳子均等分。如果将绳子按照每段长度为x，等分成m段，则n=mx，乘积为$x^{m}x^m$，因为有$x^m=x^{n\mathrm{/}x}x^m=x^\{n/x\}$，当$x^{1\mathrm{/}x}x^\{1/x\}$取最大值时$x^{m}x^m$取最大值。根据数学知识计算$x^{1\mathrm{/}x}x^\{1/x\}$的最大值，当x=3时，取到最大值。因此将绳子分为长度为3的均等分可以使乘积最大。

方法一用暴力方法，尽可能将绳子均等分为长度为3的绳子，result保存乘积，循环条件设为大于4的原因是，如果最后绳子只剩下1米，匀出一个3米的绳子凑成两个2米的绳子。

具体做法：

class Solution {
public:
    long long MAX_N = 998244353;
    long long cutRope(long long number) {
        if(number <= 3){ //不超过3直接计算
            return number - 1;
        }
        long long result = 1;
        while(number > 4){//每经历一个循环就分出一段长度为3的绳子
            result *= 3; 
            result = result % MAX_N;//取模
            number -= 3; //绳子总长度减去3
        }
        return result * number % MAX_N;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，循环n/3次。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

快速幂。整体思想和方法一相似，用快速幂的思想优化时间复杂度，快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。quick_pow函数中实现了快速幂的递归算法。用快速幂计算所有可以分为长度为3的绳子长度乘积，最后如果会多一段1米的，将1米和3米的凑成两个两米的。 具体做法：

class Solution {
public:
    long long MAX_N = 998244353;//用于取模
    
    long long cutRope(long long number) {
        if(number<=3){//绳子长度小于等于3直接返回值
            return number-1;
        }
        long long n=number/3;
        if (number % 3 == 0) {//每段都分为长度为3
            return quick_pow(n) % MAX_N;
        } else if (number % 3 == 1) {//如果都分为长度为3，最后会多一段1米的
            n--;
            return 2 * 2 * quick_pow(n) % MAX_N;//将1米和3米的凑成两个两米的
        } else {//如果都分为长度为3，最后会多一段2米的
            return 2 * quick_pow(n) % MAX_N;
        }
    }
    
    long long quick_pow (long n) {//快速幂运算
        if (n == 0) return 1;//3的0次方为1
        if (n == 1) return 3;//3的1次方为3
        long long p = quick_pow(n / 2);//把指数分成两半进行运算
        if (n % 2 == 0) {
            return p * p % MAX_N;
        }
        return 3 * p * p % MAX_N;
    } 
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，快速幂进行了二分。
• 空间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，quick_pow递归栈大小为$lo{g}_{2}nlog\_2n$。