動态規劃01--切鋼條(1)

# -*- coding: utf-8 -*-
import random

def getp(n):
    '''
    擷取一個長度為n的價格表
    '''
    p = [0 for i in range(n)]
    for i in range(n):
        p[i] = random.randint(1, n)
    return p

def cut_rod(p, n):
    if n==0:
        return 0
    else:
        q = 0
        for i in range(1, n+1):
            #從1開始切割, 切刀最後一個結束
            q = max(q, p[i-1] + cut_rod(p, n-i))
        return q

n = 10
p = getp(n)
print(p)
q = cut_rod(p, n)
print(q)