这道题是《剑指Offer》的第十四题：

给你一根长度为 n （2 <= n <= 1000） 的绳子，请把绳子剪成整数长度的 m 段（m，n都是整数，m > 1 且 n > 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。

这个题，考察的地方有两个。一是求绳子段长度的最大乘积；二是大数求余。 我们先来看第一个问题，如何求绳子段长度的最大乘积。

这边我用的是一个数学结论，即只有将绳子分为尽可能多的长度为 3 的小段，它们相乘的 结果才会最大。这里有一个异常情况，就是当 n % 3 == 1 时，此时绳子被分为若干个 3 和一个 1，因为 3 * 1 < 2 * 2，所以应该把其中一个 3 拿出来和 1 组成 4，这样才可以 获得最大值。所以，第一个问题的算法如下：

1. 如果 n <= 3，则返回 n - 1
2. numOfThree = n / 3, remainder = n % 3。如果 remainder == 1，则
返回 3^(numOfThree-1) * 4。如果 remainder == 2，则返回 3^numOfThree * 2。
其他情况，返回 3^numOfThree。

上述算法也是贪心算法的一个应用。

说完第一个问题，我们来看第二个问题 -- 大数取余。我们注意到题目中 n 的取值为[2, 1000]， 按照我们上述的算法，假如 n 取最大值 1000，那么最后的结果将是 3^332 * 4。这个数字远远 超出了 64 位机器可表达的最大整数（2^64-1），所以我们是无法对最终结果直接取余的。那么 我们怎么办呢？经过思考，我们可以利用循环，边求结果边取余。算法如下：

1. 定义变量 res 为 size_t，意思是可以表示整个机器的最大无符号整数。
2. 如果 remainder == 1，则 numOfThree = numOfThree - 1
3. 循环 i = 0; i < numOfThree; i++
    res = res * 3 % 1000000007
endif
4. 如果 remainder == 1，则 res = res * 4 % 1000000007
5. 如果 remainder == 2，则 res = res * 2 % 1000000007
6. return (int)res

这样我们就把这个题解出来了。这是我的提交记录。

=========================================补充=========================================

最大乘积的问题还可以用动态规划的方法来解决。我们假设 f(n) 代表长度为 n 的绳子的最大乘积，我们先在 长度为 i 的位置剪一刀，那么 f(n) = f(i) * f(n - i)。我们要求的 f(n) 的最大值就是 max(f(n)) = max(f(i) * f(n - i))。 这样我们就得到了动态规划的公式了。可以看到这个公式是一个递归公式，如果我们自上而下的进行计算， 会导致很多重复的运算，效率比较低。这种情况下，我们一般考虑自下而上的解决问题，这样动态规划就派上用场了。 我们知道动态规划一定要有一个数组，一维或者二维，然后还要有一个公式，用来帮助你填满数组。数组的最后一个 值就是最终的答案。现在我们公式已经有了，而且我们可以写出数组的前几个值，f(0) = 0, f(1) = 1, f(2) = 2, f(3) = 3， 接下来就可以利用动态规划快速地求出结果了。这是我的提交记录。 还有一个要注意的就是，C 语言中使用 calloc 函数时，注意数组的大小，在这道题中，我就是因为分配了大小为 n 的 数组 arr，但是需要访问 arr[n]，而导致 heap-buffer-overflow 的错误。这一点一定要注意。

值得一提的是，作为递归思想的代表例题 -- 斐波那契数列也可以用自下而上的方法解决，采用的方法也是动态规划， 感兴趣的小伙伴可以试试，这是我的提交记录。

以上。