动态规划法解剪绳子问题

1.问题：

2.分析：定义函数f(n)为长度为n的绳子剪成若干段后的最大长度乘积

若从上而下使用递归会产生大量重复问题，不如自下而上用循环依次计算f(2),f(3)等

3.代码：

def maxlength(n):

    if n==1:

        print('长度太短')

        return

    if n==2:

        print(1)

        return

    if n==3:

        print(2)

        return

    else:

        maxlist=[2,3]

        for j in range(4,n+1):

            v=int(0.5*j+1)

            maxlength=0

            for i in range(2,v):

                result=maxlist[i-2]*maxlist[j-i-2]

                if result>maxlength:

                    maxlength=result

            maxlist.append(maxlength)

        print(maxlist[n-2])