动态规划之钢条切割问题：自顶向下（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))