劍指 Offer 14- I. 剪繩子

給你一根長度為 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。

嗯就是一個數(shù)學(xué)證明吧：

切分規(guī)則：

最優(yōu)： 3 。把繩子盡可能切為多個長度為 3 的片段，留下的最后一段繩子的長度可能為 0,1,2?三種情況。

次優(yōu)： 2 。若最后一段繩子長度為 2 ；則保留，不再拆為 1+1 。

最差： 1 。若最后一段繩子長度為 1 ；則應(yīng)把一份 3 + 1 替換為 2 + 2，因為 2*2>3*1。

class Solution:
? ?def cuttingRope(self, n: int) -> int:
? ? ? ?if n<=3:return n-1
? ? ? ?if (n%3==0):return pow(3,n//3)
? ? ? ?elif(n%3==1):return ?pow(3,n//3-1)*4
? ? ? ?else:return pow(3,n//3)*2

dp思路也可以，就是開了個N+1的數(shù)組：