top down dp solution in python

1 files changed, 21 insertions, 0 deletions

diff --git a/exercises/15.1/rod_cutting.py b/exercises/15.1/rod_cutting.py
index ec24930..8c67394 100644
--- a/exercises/15.1/rod_cutting.py
+++ b/exercises/15.1/rod_cutting.py
@@ -8,6 +8,23 @@ def cutRod(p, n):
         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)
+
 class TestRodCutting(unittest.TestCase):
     def setUp(self):
         self.p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
@@ -17,5 +34,9 @@ class TestRodCutting(unittest.TestCase):
         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))
+
 if __name__ == '__main__':
     unittest.main()