題目描述
給定一根長度為n的繩子搂鲫，請把繩子剪成m段（m亥啦、n都是整數(shù)，n>1并且m>1）每币，每段繩子的長度記為k[0],k[1],…,k[m]。請問k[0]* k[1] * … *k[m]可能的最大乘積是多少琢歇？例如兰怠，當(dāng)繩子的長度是8時，我們把它剪成長度分別為2李茫、3揭保、3的三段，此時得到的最大乘積是18魄宏。
思路
這是一道動態(tài)規(guī)劃問題秸侣。整體問題的最優(yōu)解依賴于各個子問題的最優(yōu)解。首先是對于問題的拆解宠互，第一刀的時候味榛，有n-1種選擇，如何選出最優(yōu)的一刀予跌？ 在n-1個位置嘗試搏色，找到相乘最大的那一刀所在的位置。 f(n) = max{f(i)*f(n-i)}匕得。
這里最初一直沒想明白為什么這樣一刀一刀選下去就是最優(yōu)解继榆。后來思考過程如下，假設(shè)第一刀不是最優(yōu)解汁掠，那一定還有其他切法會使得乘積更大略吨，所以無論怎么切，一定會切出來兩段繩子考阱，導(dǎo)致乘積最大翠忠。那切出的每一段繩子，一定可以分解成另外兩小段的乘積乞榨。
這里的思考過程是從上至下秽之，但是在實(shí)際的操作中当娱，可以先分析最小的子問題，然后記錄子問題的解考榨，從下至上解決問題跨细。
在代碼實(shí)現(xiàn)中構(gòu)建了一個ans數(shù)組，這里的ans記錄了切繩子時對應(yīng)長度可表示的最大值河质。ans[1]就表示長度為1的長度最大值（假設(shè)繩子長度大于2）冀惭。ans[2]表示切分時，切到一段為2時的最大值掀鹅。這里要注意散休，如果繩子的長度是2，那最大是切成1和1兩段乐尊。但是如果繩子大于2戚丸，其中一段切成長度為2，那這里ans[2]最大值就是2扔嵌。ans[3]表示切了一段繩子的長度為3限府，那他最大可以用3來表示，也就是直接用一段長度為3的繩子表示对人。
1谣殊，2，3這三個長度就是基本的情況牺弄，如果長度再長就可以分解為這3個長度來組合解決了姻几。
具體的代碼實(shí)現(xiàn)如下。
代碼
def maxCutting(length):
if length<2:
return 0
if length ==2:
return 1
if length ==3:
return 2
ans =[0]*(length+1)
ans[0] = 0
ans[1] = 1
ans[2] = 2
ans[3] = 3
for i in range(4,length+1):
result = 0
end = int(i/2)+1
for j in range(1,end):
temp = ans[j] * ans[i-j]
if temp > result:
result = temp
ans[i] = result
return ans[-1]
print(maxCutting(8))
