implement top down dynamic programming approach in golang

1 files changed, 35 insertions, 0 deletions

diff --git a/exercises/15.1/rod_cutting_test.go b/exercises/15.1/rod_cutting_test.go
index 515a790..3126ee3 100644
--- a/exercises/15.1/rod_cutting_test.go
+++ b/exercises/15.1/rod_cutting_test.go
@@ -22,6 +22,30 @@ func cutRod(p []int, n int) int {
 	return q
 }
 
+func memoizedCutRodAux(p []int, n int, r []int) int {
+	if r[n] >= 0 {
+		return r[n]
+	}
+	if n == 0 {
+		return 0
+	}
+	q := -1
+	for i := 1; i <= n; i++ {
+		q = max(q, p[i]+memoizedCutRodAux(p, n-i, r))
+	}
+	r[n] = q
+	return q
+}
+
+func memoizedCutRod(p []int, n int) int {
+	r := []int{}
+	for i := 0; i <= n; i++ {
+		r = append(r, -1)
+	}
+
+	return memoizedCutRodAux(p, n, r)
+}
+
 func TestRodCutting(t *testing.T) {
 	r := []int{0, 1, 5, 8, 10, 13, 17, 18, 22, 25, 30}
 	p := []int{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}
@@ -36,4 +60,15 @@ func TestRodCutting(t *testing.T) {
 			}
 		}
 	})
+
+	t.Run("with top down dynamic programming approach", func(t *testing.T) {
+		for n := 0; n < len(p); n++ {
+			expected := r[n]
+			actual := memoizedCutRod(p, n)
+
+			if expected != actual {
+				t.Errorf("%d: expected %d, actual %d", n, expected, actual)
+			}
+		}
+	})
 }