In [73]:

    

INT_MIN = -32767

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


    

In [75]:

    

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]
for i in range(len(p)):
    print("i:",i,bottomUpCutRod(p,i))


    

    




i: 0 0
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 [ ]: