題目描述：

給你一根長度為 n 繩子，請把繩子剪成 m 段（m、n 都是整數，2≤n≤58 并且 m≥2）。 每段的繩子的長度記為k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘積是多少？

例如：當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到最大的乘積18。

分析：

書上說的有數學規律：（看注釋）

            
              # 方法一：貪婪算法
def maxProductAfterCutting(length):
    if length == 2:                   # 這3個特殊的長度，直接求出返回值
        return 1
    elif length == 3:
        return 2
    elif length == 4:
        return 4
    c=[]
    while length >= 5:               # 由數學計算得出，當長度大于5時候，每段長3，乘積最大
        length-=3                    # 巧的是，如果最后剩4，分成2*2 乘積最大，但是4正好是2*2的值。巧！
        c.append(3)
    return 3**len(c)*length

maxProductAfterCutting(6)
            
          

方法二：動態規劃。把前邊的都求出來。

（從此題首次接觸動態規劃。）

            
              # 方法二：動態規劃
def dynamic_programming(n):
    if n==2:                         # 這3個特殊的長度，直接求出返回值
        return 1
    if n==3:
        return 2
    if n==4:
        return 4
    tem_lis = [0,0,2,3,4]                 # 這個列表的前兩個數無所謂，因為根本用不到
    
    for i in range(5,n+1):                # 外循環：繩子長度從5到n  注意range()前閉后開。
        maxx = 0 
        for j in range(2,i//2+1):         # 內循環：所有可能的組合：2，3，4...中間值
            tem = tem_lis[j]*tem_lis[i-j] # i-j 為另一段長度
            if tem > maxx:
                maxx = tem                # maxx存放乘積最大的值
        tem_lis.append(maxx)              # tem_list中存儲的是所有的可能繩子長度的解
    #print(tem_lis)
    return tem_lis[n]

dynamic_programming(8)
                
            
          

?