add top down dynamic programming solution

1 files changed, 26 insertions, 0 deletions

diff --git a/exercises/15.1/rod_cutting.rb b/exercises/15.1/rod_cutting.rb
index ce9f058..2ba5354 100644
--- a/exercises/15.1/rod_cutting.rb
+++ b/exercises/15.1/rod_cutting.rb
@@ -10,6 +10,26 @@ def cut_rod(p, n)
   q
 end
 
+def memoized_cut_rod_aux(p, n, r)
+  return r[n] if r[n] >= 0
+  return 0 if n == 0
+
+  q = -1
+  1.upto(n) do |i|
+    q = [q, p[i] + memoized_cut_rod_aux(p, n-i, r)].max
+  end
+  r[n] = q
+  q
+end
+
+def memoized_cut_rod(p, n)
+  r = []
+  0.upto(n) do |i|
+    r[i] = -1
+  end
+  memoized_cut_rod_aux(p, n, r)
+end
+
 class RodCuttingTest < Minitest::Test
   def setup
     @prices =      [ 0,  1,  5,  8,  9, 10, 17, 17, 20, 24, 30]
@@ -22,4 +42,10 @@ class RodCuttingTest < Minitest::Test
       assert_equal @max_revenue[n], cut_rod(@prices, n), "n: #{n}"
     end
   end
+
+  def test_top_down_dynamic_programming_approach
+    0.upto(10) do |n|
+      assert_equal @max_revenue[n], memoized_cut_rod(@prices, n), "n: #{n}"
+    end
+  end
 end