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