implement bottom up dp in pythonHEADmain

1 files changed, 18 insertions, 0 deletions

diff --git a/exercises/15.1/rod_cutting.py b/exercises/15.1/rod_cutting.py
index 8c67394..7d7609c 100644
--- a/exercises/15.1/rod_cutting.py
+++ b/exercises/15.1/rod_cutting.py
@@ -25,6 +25,20 @@ def topDownCutRod(p, n):
         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]
@@ -38,5 +52,9 @@ class TestRodCutting(unittest.TestCase):
         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()