題目
給你一根長度為n的繩子，請把繩子剪成m段 (m和n都是整數，n>1并且m>1)每段繩子的長度記為k[0],k[1],…,k[m].請問k[0]k[1]…*k[m]可能的最大乘積是多少？例如，當繩子的長度為8時，我們把它剪成長度分别為2,3,3的三段，此時得到的最大乘積是18.
解題思想
動态規劃(具體解法及思路見代碼注釋)
class Solution():
def maxProfuctAfterCutting(self,length):
if length < 2:
return 0
if length == 2:
return 1
if length == 3:
return 2
products = [0,1,2,3]
for i in range(4,length+1):
max = 0
for j in range(1,i//2+1):
# 思路：每次求解值時将其他小于需要求解的長度是都列出來放在一個數組裡
# 如：求長度為5，最優解數組裡必須得有長度為1,2,3,4的最優解值
# 注：此處使用清單儲存最優解數組是為了性能優化，雖然遞歸求解也能解出，但會造成大量重複執行
temp = products[j] * products[i-j]
if temp>max:
max = temp
products.append(max)
return products[length]