From 28bb5a9343eb4d747fc17487e38c093ba9760885 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 21 Nov 2021 18:07:39 -0700 Subject: top down dp solution in python --- exercises/15.1/rod_cutting.py | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'exercises') 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() -- cgit v1.2.3