利用動态規劃的思想求最優解

源自《劍指offer》中的剪繩子問題，書中使用的是C++，但是我更喜歡用python實作。這裡按照從上而下的順序計算，也就是說我們先得到f(2)、f(3)，再得到f(4)、f(5)，直到得到f(n)...

# -*- coding:utf-8 -*-

#利用動态規劃的思想

#給你一根長度為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.

def maxProductAfterCutting(length):

    ####  code write here###

    # for j in range(temp):  需要注意的就是，range(temp)是從0開始的，也就是會得到0,1,3...temp-1 的循環

    if length<2:

        return 0

    if length==2:

        return 1

    if length==3:

        return 2

    #=[None]*4

    products=[None]*length

    #products.append(0)

    products[0]=1

    products[1]=2

    products[2]=3

    for i in range(4,length+1):

        max_length=0

        temp=i/2+1

        for j in range(1,temp):

            product=products[j-1]*products[i-j-1]  #因為python的清單操作下标是從0開始的，是以需要減1

            if max_length<product:

                max_length=product

                products[i-1]=max_length   #更新最優解，最優解存儲

    return products[i-1]

#test驗證效果

print maxProductAfterCutting(4)

print maxProductAfterCutting(8)

print maxProductAfterCutting(10)

print maxProductAfterCutting(3)

####end code here ############