Chapter 15.1 动态规划—钢条切割

# 切钢管
#自顶向下递归实现（指数级时间复杂度）
def cutRod1(p,n):
    if n==0:
        return 0
    q=-99999
    for i in range(1,n+1):
        q=max(q,p[i-1]+cutRod1(p,n-i))
    return q

#动态规划法时间复杂度为O(n²)
#带备忘的自顶向下
def memorizedCutRod(p,n):
    r=[]
    for i in range(n+1):
        r.append(-9999)
    return memorizedCutRodAux(p,n,r)

def memorizedCutRodAux(p,n,r):
    if r[n]>=0:
        return r[n]
    if n==0:
        q=0
    else:
        q=-9999
        for i in range(1,n+1):
            q=max(q,p[i-1]+memorizedCutRodAux(p,n-i,r))
    r[n]=q
    return q

#自底向上
def bottomupCutRod(p,n):
    r = []
    for i in range(n + 1):
        r.append(-9999)
    r[0]=0
    for j in range(1,n+1):
        q=-9999
        for i in range(1,j+1):
            q=max(q,p[i-1]+r[j-i])
        r[j]=q
    return r[n]

重构解
def extendedBottomUpCutRod(p,n):
    r=[]
    s=[]
    for i in range(n+1):
        r.append(-9999)
    for i in range(n+1):
        s.append(-9999)
    for j in range(1,n+1):
        q=-9999
        for i in range(1,j+1):
            if q<p[i-1]+r[j-i]:
                q=p[i-1]+r[j-i]
                s[j]=i
            r[j]=q
    return r,s

def printCutRodSolution(p,n):
    (r,s)=extendedBottomUpCutRod(p,n)
    while n>0:
        print(s[n])
        n=n-s[n]

if __name__=="__main__":
    p=[1,5,8,9,10,17,17,20,24,30]
    print(printCutRodSolution(p,9))