diff options
Diffstat (limited to 'exercises')
| -rw-r--r-- | exercises/15.1/rod_cutting.py | 21 |
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() |