From 5e27791a0cd9fdf8d5ff5afd1a54d4d4031ba5fe Mon Sep 17 00:00:00 2001
From: mo khan <mo@mokhan.ca>
Date: Sun, 21 Nov 2021 16:53:41 -0700
Subject: add top down dynamic programming solution

---
 exercises/15.1/rod_cutting.rb | 26 ++++++++++++++++++++++++++
 notes.md                      |  5 +++--
 2 files changed, 29 insertions(+), 2 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
diff --git a/notes.md b/notes.md
index a857010..b4d565c 100644
--- a/notes.md
+++ b/notes.md
@@ -1560,7 +1560,7 @@ CUT-ROD(p, n)
     return 0
   q = -1
   for i = 1 to n
-    q = max(q, p[i] + CUT-ROD(p, n-1))
+    q = max(q, p[i] + CUT-ROD(p, n-i))
   return q
 ```
 
@@ -1579,8 +1579,9 @@ MEMOIZED-CUT-ROD-AUX(p, n, r)
   return r[n] if r[n] >= 0
   return 0 if n == 0
 
+  q = -1
   for i = 1 to n
-    q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-1, r)
+    q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r)
   r[n] = q
 
   return q
-- 
cgit v1.2.3