14-剪绳子

题目：给你一根长度为n的绳子，请把绳子剪成m段（m,n都是整数，且都大于1），每段绳子的长度记为k[0],k[1],...k[m]。请问k[0]*k[1]*k[2]*...*k[m]可能的最大成绩是多少？

def max_product_cut(n):
    if n<2:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 2
    i = 4
    j = 1
    products = [0 for i in range(n+1)]
    products[1] = 1
    products[2] = 2
    products[3] = 3

    while i<=n:
        max = 0
        j=2
        while j<=i//2:
            res = products[j]*products[i-j]
            if max<res:
                max = res
            j+=1
        products[i] = max

        i+=1

    return products[-1]

注：

使用动态规划，products[i]存储长度为i的绳子最大乘积。本地巧妙在于，整段绳子n的最大乘积，只要求出n/2的最大乘积即可，剩下的部分在数组的前半部分已经计算存储。状态方程为f(n)=max(f(i)*f(n-i))