14.2.剪绳子 (Medium)*

题目描述*

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

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

代码*

动态规划好像 8 太行，还是用数学方法 8。改成 unsigned 就行了。

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) {
            return n - 1;
        }
        if(n == 4) {
            return 4;
        }
        unsigned int res = 1;
        while (n > 4){
            n -= 3;
            res *= 3;
            res = res % 1000000007;
        }

        res *= n;
        return  res % 1000000007;
    }
};

最后更新: July 23, 2022