cutting a rod

I studied cuttingrod dp alogorithm.

first cuttingrod is recursive function
cuttingRodDP is dynamic problem.

If we want to use by using recursive function
to speed up. we have to use memoized array

def cuttingRod(s, arr):

    m = arr[s-1]
    for i in range(1,int(s/2)+1):
        left=  i
        right =s-i
        val = cuttingRod(left, arr) + cuttingRod(right,arr)
        print(left, right, val)
        m= max(m, val )

    return m

def cuttingRodDP(s, arr):

    m = [0 for i in range(len(arr)+1)]
    for i in range(1, len(arr)+1):
        m[i]= arr[i-1]

    maxValue =0
    for i in range(1, len(arr)+1):
        for j in range(1,i+1):
           maxValue =  max(maxValue, m[j] + m[i-j])
        m[i] = maxValue

    return maxValue

arr= [ 1 ,  5,   8 ,  9 , 10,  17,  17,  20]
print(cuttingRod(len(arr), arr))

print(cuttingRodDP(len(arr), arr))


Popular posts from this blog

codefights smooth sailing ( CommonCharacterCount)

How to remove 8443 port in URL in tomcat