动态规划之钢条切割问题：自顶向下（Python实现）

#
#钢条切割问题：自顶向下（由大到小）
#
#自顶向下递归实现
# def CUT_ROD(p,n):
#     if n==0:
#         return 0;
#     q = -1000
#     for i in range(1,n):
#         q = max(q,p[i]+CUT_ROD(p,n-i))
#     return q
#获得最大值
def max(a,b):
    maxData = a;
    if maxData < b:
        maxData = b;
    return maxData
# 备忘机制的CUT-ROD
def MEMOIZED_CUT_ROD_AUX(p, n, r):
    # print("p=",p)
    # print("n=",n)
    # print("r=",r)
    n = n - 1
    if r[n] >= 0:
        return r[n]
    if n == 0:
        q = 0
    else:
        q = -9999
        for i in range(1, n):
            # print(int(p[i]))
            q = max(q, int(p[i]) + int(MEMOIZED_CUT_ROD_AUX(p,n-i,r)))
    r[n] = q
    return q
def MEMOIZED_CUT_ROD(p,n):
    r = {}
    for i in range(0,n):
        r[i] = -9999
    return MEMOIZED_CUT_ROD_AUX(p,n,r)
if __name__ == '__main__':
    p = [1,5,8,9,10,17,17,20,24,30]
    #长度  i   0   1  2 3 4 5 6 7 8 9 10
    #价格 pi      0  1  5 8 9 10  17  17  20  24  30
    n = 20
    print("最大的收益：",MEMOIZED_CUT_ROD(p,10))