例如，當繩子的長度是8時蔚舀，我們把它剪成長度分別為2饵沧、3、3的三段赌躺，此時得到的最大乘積是18狼牺。
示例 1：
輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1
示例 2:
輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
法一 貪心 + 動態(tài)回歸
def cuttingRope(n):
if n <= 3:
return n - 1
products = [0] * (n + 1)
products[0], products[1], products[2], products[3] = 0, 1, 2, 3
# 計算長度為i的繩子的最優(yōu)解
for i in range(4, n + 1):
max1 = 0
for j in range(1, i // 2 + 1):
pro = products[j] * products[i - j]
if max1 < pro:
max1 = pro
products[i] = max1
return products[n]
print(cuttingRope(10))
print(cuttingRope(3))
法二 列舉找規(guī)律
列舉前幾組可得到，每段繩子都為3或者2時礼患，乘機最大是钥。
以3為基礎(chǔ)切割繩子，結(jié)果只有三種情況：
1讶泰、繩子可以被3整除
2、繩子除3余1
3拂到、繩子除3余2
def cuttingRope(n):
#繩長小于3
if n <= 3:
return n-1
#繩長大于3時的處理
a = n//3
b = n%3
#繩長能被3整除痪署，全部切成3
if b == 0:
mul = 3**a
#繩長除3余1，證明有可以被分成n個3和一個4兄旬，將4分割成2*2
elif b == 1:
mul = 3**(a-1)*4
#繩長除3余2狼犯，證明有可以被分成n個3和一個5，將4分割成3*2
else:
mul = 3**a*2
return mul
