14

# 动态规划
# 1.最优解；2.分解成子问题

# 比如算f(8) 就把 f(1)f(7) f(2)f(6) f(3)f(5) f(4)f(4) 之前算出来的数字 重新算一遍即可
def maxProductAfterCutting_solution1(lenth):
    if lenth == 0 or lenth == 1:
        return 0
    if lenth == 2:
        return 1
    if lenth == 3:
        return 2

    products = [0, 1, 2, 3]

    for i in range(4, lenth + 1):
        max = 0
        for j in range(1, i // 2 + 1):
            if products[j] * products[i - j] > max:
                max = products[j] * products[i - j]
        # 跟新index的值
        products.insert(lenth, max)
    print(products)
    return products[lenth]


# print(maxProductAfterCutting_solution1(4))