給你一根長度為n的繩子，請(qǐng)把繩子剪成m段谆甜，記每段繩子長度為k[0],k[1]...k[m-1],求k[0]k[1]...k[m-1]的最大值垃僚。已知繩子長度n為整數(shù)，m>1(至少要剪一刀规辱，不能不剪)谆棺，k[0],k[1]...k[m-1]均要求為整數(shù)。
例如罕袋，繩子長度為8時(shí)改淑，把它剪成3-3-2，得到最大乘積18浴讯；繩子長度為3時(shí)朵夏，把它剪成2-1，得到最大乘積2
我們假定繩子長度為n兰珍，由于題目要求至少剪一刀侍郭，我們假設(shè)剪一刀后，將繩子切為i 和n-i兩段掠河，則f(n) = max(f(i) * f(n-i))亮元。
舉個(gè)例子來幫助我們整理思路：假設(shè)現(xiàn)在n=20，我們將其剪為5 和15唠摹，而求f(15) 時(shí)爆捞，我們將其剪為5 和10，我們發(fā)現(xiàn)子問題在求解上有重合勾拉。所以我們先求解子問題煮甥，保存子問題結(jié)果，自底向上求解最優(yōu)解藕赞。
tips:當(dāng)我們將繩子切為i 和 n -i 兩段后成肘，f(i) ，f(n-i）與f(n)在求解時(shí)有些許不同：對(duì)于題目要求至少剪一刀斧蜕，所以對(duì)n來說双霍，不能不剪；而對(duì)于f(i),f(n-i), 若其不剪結(jié)果比剪后結(jié)果大，則保持其完整狀態(tài)洒闸。
那這個(gè)剪與不剪的邊界是多少染坯？下面我們簡單來證明一下：
假設(shè)n是偶數(shù)，我們只切一刀丘逸，則f(n) = (n/2) * (n/2), 令f(n) >= n;求得n>=4;
假設(shè)n是奇數(shù)单鹿，我們切一刀后，fn = (n +1)/2 * (n-1)/2, 令f(n) >= n;求得n>4;
所以切與不切的邊界為n=4
即對(duì) i<4 (或n-i <4)時(shí)深纲，f(i) = i仲锄， 即不切比切結(jié)果更大。而當(dāng)n < 4時(shí)囤萤，至少f(n) 為切一刀后的最大結(jié)果昼窗。
def cut_rope(n):
if n < 2:
return 0
if n == 2:
return 1 # 1*1
if n == 3:
return 2 # 1 * 2
# 將其切為i， n-i兩部分
area_max = {}
area_max[0] = 0
area_max[1] = 1
area_max[2] = 2
area_max[3] = 3 # 不切時(shí)最大
# 從n=4開始涛舍，不切的最大值小于等于切后的最大值
m = 4
while m <= n:
t = 0
for i in range(1, m//2 + 1):
t = max(t, area_max[i] * area_max[m-i])
area_max[m] = t
m += 1
return area_max[n]
# cut_rope(10)
36
