rod

rod.py

import numpy as np

def cutrod(p,n):
    if n == 0:
        return 0
    q = -1*np.inf
    for i in range(n):
        i_ = i+1
        q = np.max([q, p[i_-1] + cutrod( p,n - i_) ])
    return q

def cutrod_TopDown(p,n):
    d = dict()
    return cutrodTopDownHelper(p,n,d)



def cutrodTopDownHelper(p,n,d):
    if n==0:
        return 0
    
    q = -1*np.inf
    for i in range(n+1):
        if i!= 0:
            if d.get(n-i) == None:
                d[n-i] = cutrodTopDownHelper(p,n-i,d)
            q = np.max(q, p[i-1] + d[n-i])
    return q


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

if __name__ == "__main__":
    
    import cProfile
    p = [1,5,8,9,10,17,17,20,24,30]
    
    cProfile.run("print(cutrodBottomUp(p,8))")