python 3.2 实现钢管划分 动态划分

python 3.2 实现钢管划分 动态划分

动态规划的关键就在于问题的解决方案取决于子问题的解决方案

def bottom_up_cut_rod(p,n):
    i=0
    r=[0]*(n+1)
    for j in range(1,n+1):
        q=-1
        for i in range(1,j+1):
            q=max(q,p[i]+r[j-i])
        r[j]=q
    return r[n]