# RodCutting and learning Dynamic Programming

I tried to learn dynamic programming going from recursion to memoized version with the RodCutting problem: Returns the best obtainable price for a rod of length n and price[] as prices of different pieces.

Have you any suggestions on the code (or the way to make test), i tried to keep as simple and generic to mimic on others similar problems (i could have erase the n from input and calculate inside the function but it would confuse the solution).


"""
Inspiration of DP from: https://wellsr.com/python/optimizing-recursive-functions-with-python-memoization/
"""

def cutRod(price, n):
"""
Returns the best obtainable price for a rod of length n
and price[] as prices of different pieces
"""
res = price[n-1] # One piece without cut
for i in range(n-1):
res = max(res,price[i]+cutRod(price,n-(i+1))) #i+1 cut
return res

def cutRodMemo(price, n):
"""
Returns the best obtainable price for a rod of length n
and price[] as prices of different pieces
"""
# 1.Define memo table
memo = [None]*n
memo[0] = price[0]
# 2.Memoize recursive approach
def cutRodAux(price,n,memo):
if memo[n-1]:
return memo[n-1]
res = price[n-1]
for i in range(n-1):
res = max(res,price[i]+cutRodAux(price,n-(i+1),memo))
memo[n-1]= res
return res
return cutRodAux(price,n,memo)

if __name__ == '__main__':
import unittest
f = cutRod

class Test(unittest.TestCase):
def test(self):
args = [(([10,24,30,40],4),48),
(([1, 5, 8, 9, 10, 17, 17, 20],8),22)
]
for i,o in args:
prices,size = i
self.assertEqual(cutRod(prices,size), o)
self.assertEqual(cutRodMemo(prices,size), o)

unittest.main()



2. f = cutRod - f seems unused
4. Removing n from the input would actually be a good idea as right now you are providing redundant information.