implement bottom up dp solution

1 files changed, 18 insertions, 0 deletions

diff --git a/exercises/15.1/rod_cutting.rb b/exercises/15.1/rod_cutting.rb
index 2ba5354..8bdb694 100644
--- a/exercises/15.1/rod_cutting.rb
+++ b/exercises/15.1/rod_cutting.rb
@@ -30,6 +30,18 @@ def memoized_cut_rod(p, n)
   memoized_cut_rod_aux(p, n, r)
 end
 
+def bottom_up_cut_rod(p, n)
+  r = [0]
+  1.upto(n) do |j|
+    q = -1
+    1.upto(j) do |i|
+      q = [q, p[i] + r[j-i]].max
+    end
+    r[j] = q
+  end
+  r[n]
+end
+
 class RodCuttingTest < Minitest::Test
   def setup
     @prices =      [ 0,  1,  5,  8,  9, 10, 17, 17, 20, 24, 30]
@@ -48,4 +60,10 @@ class RodCuttingTest < Minitest::Test
       assert_equal @max_revenue[n], memoized_cut_rod(@prices, n), "n: #{n}"
     end
   end
+
+  def test_bottom_up_dynamic_programming_approach
+    0.upto(10) do |n|
+      assert_equal @max_revenue[n], bottom_up_cut_rod(@prices, n), "n: #{n}"
+    end
+  end
 end