給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長度的 m 段（m、n都是整數(shù)，n>1并且m>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。
示例 1：

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1

示例 2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

題解

最開始寫這個題的時候考慮的是動態(tài)規(guī)劃，但是由于有最小段數(shù)的限制，并且乘積還可能過大，超出long的范圍，所以使用動態(tài)規(guī)劃過于麻煩，多次修改提交都以失敗告終。
通過查看題解，發(fā)現(xiàn)可以使用貪心算法求解，其中提到要將繩子盡可能多的拆分為長度為3的小段。
這是因為任何自然數(shù)都可以用2和3組合獲得，而2的乘積小于3的乘積，所以才會盡可能多的拆成3，而對于最后一段的拆分，如果最后一段長度小于5，就不應該再拆分了，再拆分的話，就會獲得1，背離了拆成2和3。
最后的解：

public int cuttingRope(int n) {
    int m = 4;
    // 如果n小于4, 返回n-1
    if (n < m) {
        return n - 1;
    }
    // 這里需要使用long來存儲值,用int會溢出
    long res = 1, i = 3, p = 1000000007;
    while (n > m) {
        // 每次都余姚求余,要不容易溢出long的最大值
        res = (res * i) % p;
        // 如果n>4的話,截掉長度為3的段
        n -= i;
    }
    // 這里還有小于等于4的一段,這段無法再拆分了,直接乘上去即可
    return (int) ((res * n) % p);
}