import unittest

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

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

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

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

    return r[n]

class TestRodCutting(unittest.TestCase):
    def setUp(self):
        self.p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
        self.r = [0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30]

    def test_recursive(self):
        for n in range(10):
            self.assertEqual(self.r[n], cutRod(self.p, n))

    def test_top_down(self):
        for n in range(10):
            self.assertEqual(self.r[n], topDownCutRod(self.p, n))

    def test_bottom_up(self):
        for n in range(10):
            self.assertEqual(self.r[n], bottomUpCutRod(self.p, n))

if __name__ == '__main__':
    unittest.main()