In [16]:

    

def cutRod(p,n):
    if n <= 0:
        return 0
    q = -sys.maxsize - 1
    for i in range(n):
        q = max(q, p[i] + cutRod(p, n-i-1))
    return q


    

In [35]:

    

def memoizedCutRod(p,n):
    r = []
    for i in range(n+1):
        r.append(-1)
    return memoizedCutRodAux(p,n,r)

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


    

In [38]:

    

p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 1, 5, 8, 9, 10]


    

In [39]:

    

for i in range(1,len(p)):
    print("i:",i,memoizedCutRod(p,i))


    

    




i: 1 1
i: 2 5
i: 3 8
i: 4 10
i: 5 13
i: 6 17
i: 7 18
i: 8 22
i: 9 25
i: 10 30
i: 11 31
i: 12 35
i: 13 38
i: 14 40
i: 15 43
i: 16 47
i: 17 48
i: 18 52
i: 19 55
i: 20 60
i: 21 61
i: 22 65
i: 23 68
i: 24 70

In [40]:

    

for i in range(1,len(p)):
    print("i:",i,cutRod(p,i))


    

    




i: 1 1
i: 2 5
i: 3 8
i: 4 10
i: 5 13
i: 6 17
i: 7 18
i: 8 22
i: 9 25
i: 10 30
i: 11 31
i: 12 35
i: 13 38
i: 14 40
i: 15 43
i: 16 47
i: 17 48
i: 18 52
i: 19 55
i: 20 60
i: 21 61
i: 22 65
i: 23 68
i: 24 70

In [ ]: