Introduction
Dynamic Programming can be thought of as an approach of breaking a complex problem into subproblems, solving each of these subproblems one time only, and saving their solutions for future use. As we will see later in this blog, this approach offers efficiency and modularity benefits over other approaches that we will be exploring in a bit.
Dynamic Programming Techniques
When we talk about Dynamic Programming, we must as well discuss its techniques. Below are the techniques:

Memoization
: the technique is known as “Memoization” (not to be confused with Memorization). Memoization is a technique for improving the performance of a recursive function/algorithm. In other words, it offers an optimization to speed up programs by storing the solutions of expensive function calls and returning the cached solution when the same inputs are fed to the program again. 
Tabulation
: another optimization technique used in Dynamic Programming is Tabulation (also known as the BottomUp technique). As you might guess, this technique uses a tabular approach by first filling up a table, then solve the original problem based on the solutions filled in the table. We will not be looking into this technique in this blog but Memoization.
Now that we have discussed what Dynamic Programming is and its techniques. Now, let’s step into the coding part. We are going to use the Fibonacci Sequence problem as an example, solving it using three distinct approaches. If you are reading about the Fibonacci Sequence for the first time, think of it as the series of numbers in which the next number is found by adding up the two numbers before it. For example, the sequence
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
forms the first ten entries of the Fibonacci series. With that explained, a Fibonacci(10)
will result in 55.
The first step to starting any of the approaches is to define a function to help us track the execution time consumed by each of the solutions we will be presenting:
// for tracking program's execution time
func trackTime(start time.Time, result int, name string) {
elapsed := time.Since(start)
log.Printf("> %s solution  result: %v  took: %s", name, result, elapsed)
}
Recursion
One quick approach that is likely to come to mind when faced with the Fibonacci Sequence problem above is to use a Recursion. Perfect. But, let’s see the implementation and efficiency of this approach:
// the recursive function approach definition
func expensiveFib(n int) int {
if n < 2 {
return n
}
result := expensiveFib(n1) + expensiveFib(n2)
return result
}
Running the Recursion solution with an input of 50
will result in 12586269025
with an execution time of roughly 1m and 6.413943065s
. So, why does it take this long time?
Simply put, the reason is due to the recursive call of the function; we are checking if the input is less than 2. If yes, we return the input, and move to the next stack of the function calls.
In this case, the returned input would be either 1 or 0. On the other hand, if 2 is not greater than the input, we call the function twice; one time with the input  1 and the second time with the input  2, and sum the result of both calls.
The image below depicts the process (using an input of 5):
Loop
Another approach that is likely to be thought of is to use a loop. Let’s see the implementation and efficiency of this approach:
// the loop approach definition
func fibByLoop(n int) int {
fibBox := []int{0, 1}
for i := 0; i < n; i++ {
v := fibBox[i] + fibBox[i+1]
fibBox = append(fibBox, v)
}
result := int(fibBox[n])
defer trackTime(time.Now(), result, "Loop")
return result
}
Running the Loop solution with an input of 50
will result in 12586269025
with an execution time of roughly 2.356µs
. That seems way faster than the Recursive approach. From 1m and 6.413943065s
down to 1.428µs
. Impressive!
So what is the algorithm behind this solution?
The answer is, we used an iterative approach. Let us review the steps below:
 We create and initialize an array, namely
fibBox
to values of0 and 1
(those are the starting point for the Fibonacci Sequence).  In the loop, we created another variable namely
i
, and initialized it to0
. This is used as an index offibBox
in each iteration.  We iterate over the parameter
n
and check ifi < n
. As long asi < n
, we decrementn
.  In each iteration, we sum up the values of current and next indexes in
fibBox
(e.g.,fibBox[i] + fibBox[i+1]
), and append the result tofibBox
. Once the loop is done running, we return the value offibBox[n]
; that is the result of the Fibonacci Sequence of the input we were given.
Memoization
Another approach would be Memoization. Let’s see the implementation and efficiency of this approach. As explained above, Memoization improves the performance of Recursion, which means we should start by implementing a recursive function first (we will use the one defined above) then, we will improve its efficiency by storing and reusing the solutions in the cache.
// we made a few changes to the one used used above in the Recursion solution
func refinedExpensiveFib(n int, cache map[int]int) int {
if n < 2 {
cache[n] = n // n is either 0 or 1
return n
}
// check cache before calling the function recursively
if _, ok := cache[n1]; !ok {
// we haven't come across n1 before
cache[n1] = refinedExpensiveFib(n1, cache)
}
// At this point, n1 is in the cache. You could log n1
if _, ok := cache[n2]; !ok {
// we haven't come across n1 before
cache[n2] = refinedExpensiveFib(n2, cache)
}
// At this point, n2 is in the cache. You could log n2
// returns the summed up cache
return cache[n1] + cache[n2]
}
Finally, we define a memoize()
that will consume refinedExpensiveFib()
:
// the memoize approach definition
func memoize(n int) int {
cache := make(map[int]int)
result := make([]int, n)
for i := 1; i <= n; i++{
result[i1] = refinedExpensiveFib(i, cache)
}
return result[n1]
}
Running the Memoization solution with an input of 50
will result in 12586269025
with an execution time of roughly 181ns.
That is absolutely way faster and more efficient than the Loop solution which resulted in 2.356µs
. In addition to performance gain, we also have the flexibility of making the solution modular and somehow readable.
The full program below [I would advise that you run each solution individually]:
package main
import (
"log"
"time"
)
func main(){
input := 50
//Recursion
start := time.Now()
result := expensiveFib(input)
defer trackTime(start, result, "Recursion")
//Loop
fibByLoop(input)
//Memoization
memoize(input)
}
/* function for measuring the execution the */
func trackTime(start time.Time, result int, name string) {
elapsed := time.Since(start)
log.Printf("> %s solution  result: %v  took: %s", name, result, elapsed)
}
/* Recursion solution */
func expensiveFib(n int) int {
if n < 2 {
return n
}
result := expensiveFib(n1) + expensiveFib(n2)
return result
}
/* using loop */
func fibByLoop(n int) int {
fibBox := []int{0, 1}
for i := int(0); i < n; i++ {
v := fibBox[i] + fibBox[i+1]
fibBox = append(fibBox, v)
}
result := int(fibBox[n])
defer trackTime(time.Now(), result, "Loop")
return result
}
/* Memoization solution */
// using memoization
func refinedExpensiveFib(n int, cache map[int]int) int {
if n < 2 {
cache[n] = n // n is either 0 or 1
return n
}
// check cache before calling the function recursively
if _, ok := cache[n1]; !ok {
// we haven't come across n1 before
cache[n1] = refinedExpensiveFib(n1, cache)
}
// At this point, n1 is in the cache. You could log n1
if _, ok := cache[n2]; !ok {
// we haven't come across n2 before
cache[n2] = refinedExpensiveFib(n2, cache)
}
// At this point, n2 is in the cache. You could log n2
// returns the summed up cache
return cache[n1] + cache[n2]
}
func memoize(n int) int {
cache := make(map[int]int)
bucket := make([]int, n)
for i := 1; i <= n; i++{
bucket[i1] = refinedExpensiveFib(i, cache)
}
result := bucket[n1]
defer trackTime(time.Now(), result, "Memoization")
return result
}
Running the main()
will result in:
2020/09/19 21:44:40 > Recursion solution  result: 12586269025  took: 2m18.47818166s
2020/09/19 21:42:22 > Loop solution  result: 12586269025  took: 2.356µs
2020/09/19 21:44:40 > Memoization solution  result: 12586269025  took: 181ns
Memoization offers a modularity and code readability benefits over the Loop approach; we saw how we improved/refined the logic in expensiveFib()
(we named it refinedExpensiveFib()
), then we called it inside the memoize()
.
Conclusion
In this blog, we explored three different approaches to solving the Fibonacci Sequence problem. We weighed each approach’s efficiency, readability, and modularity. You can read more on Memoization in this blog: Dynamic Programming and Memoization and the Compute versus Storage Tradeoff
I hope you enjoyed reading through as much as I enjoyed writing this blog.
Let’s keep “Go”ing :)