write recursive 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
new file mode 100644
index 0000000..ec24930
--- /dev/null
+++ b/exercises/15.1/rod_cutting.py
@@ -0,0 +1,21 @@
+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
+
+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))
+
+if __name__ == '__main__':
+    unittest.main()