劍指 Offer 14- II. 剪繩子 II

給你一根長度為 n 的繩子，請把繩子剪成整數(shù)長度的 m 段（m、n都是整數(shù)，n>1并且m>1），每段繩子的長度記為 k[0],k[1]...k[m - 1] 。請問 k[0]*k[1]*...*k[m - 1] 可能的最大乘積是多少？例如，當(dāng)繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18。

答案需要取模 1e9+7（1000000007），如計算初始結(jié)果為：1000000008，請返回 1。

由于要取模，取?？隙ㄊ敲坑嬎阋淮稳∧Ｒ淮卫?，所以這時候不能用dp了不然會亂。

貪心的話就是要盡量拆3。

重點(diǎn)是要判斷=4的邊界條件，這時候不用拆了，就是*4，如果再按3來拆就拆成1*3=3<4了，所以會錯。

class?Solution:

????def?cuttingRope(self,?n:?int)?->?int:

????????if?n<=3:return?n-1

????????res=1

????????while?n>4:

????????????res=res*3%1000000007

????????????n-=3

????????return?res*n%1000000007