题解 | #剪绳子#

class Solution:
    # 3最适合做底：因为3^2>2^3，3^4>4^3。往上往下都是3为底的情况最大。
    # 特殊情况：number = 4，2 * 2 > 3 * 1，因为1在乘法中不起作用。
    # 也就是说，尽量乘3，且要保证剩下的是3或者2，而不能是1
    def cutRope(self, number: int) -> int:
        if number <= 3:
            return number - 1
        count = 1
        # 这里可以用快速幂降低时间复杂度为log(n/3)
        # number mod 3 = 1,先弹出因子4; number mod 3 = 2，先弹出因子2
        # 然后经典快速幂方法
        while number > 3:
            if number == 4:
                count *= 4
                return count
            count *= 3
            number -= 3
        return number * count