implement bottom up solution in golang

1 files changed, 30 insertions, 0 deletions

diff --git a/exercises/15.1/rod_cutting_test.go b/exercises/15.1/rod_cutting_test.go
index 3126ee3..b7808ab 100644
--- a/exercises/15.1/rod_cutting_test.go
+++ b/exercises/15.1/rod_cutting_test.go
@@ -46,6 +46,25 @@ func memoizedCutRod(p []int, n int) int {
 	return memoizedCutRodAux(p, n, r)
 }
 
+func bottomUpCutRod(p []int, n int) int {
+	if n == 0 {
+		return 0
+	}
+	r := []int{0}
+	for i := 1; i <= n; i++ {
+		r = append(r, -1)
+	}
+	for j := 1; j <= n; j++ {
+		q := -1
+		for i := 1; i <= j; i++ {
+			q = max(q, p[i]+r[j-i])
+		}
+		r[j] = q
+	}
+
+	return r[n]
+}
+
 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}
@@ -71,4 +90,15 @@ func TestRodCutting(t *testing.T) {
 			}
 		}
 	})
+
+	t.Run("with bottom up dynamic programming approach", func(t *testing.T) {
+		for n := 0; n < len(p); n++ {
+			expected := r[n]
+			actual := bottomUpCutRod(p, n)
+
+			if expected != actual {
+				t.Errorf("%d: expected %d, actual %d", n, expected, actual)
+			}
+		}
+	})
 }