剑指14-II：剪绳子II

传送门

leetcode

题目描述

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（m、n 都是整数，n > 1 并且 m > 1），
每段绳子的长度记为 k[1], ..., k[m]。k[1]*...*k[m] 可能的最大乘积是多少？
例如，当绳子的长度是 8 时，把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

C++ 代码 - leetcode

class Solution {
public:
    const int MOD = 1e9 + 7;

    int cuttingRope(int n) {
        if (n <= 3) return n - 1;

        long res = 1;
        while (n > 4) {
            res *= 3; // 3最优
            res %= MOD;
            n -= 3;
        }
        // 循环结束，n 只剩下 1,2,3,4
        // 4最优，可以分成 1 * 3 or 2 * 2
        return (res * n) % MOD;
    }
};