Fibonacci with golang dynamic

Fibonacci is very famous example for recursion in programming, however if we use recursive the function, the time complex is 2^n, so we will use dynamic to resolve this problem.

Fibonacci is a sequence number with formal

F0 = 0, F1 = 1,
Fn = Fn-2 + Fn-1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, ...

The ideas is very simple, we will calculate the value fibonacci from 0 to n and saving to the map. Return the map[n]

func fibonacci(n int) int {
fibMap := make(map[int]int)
for i := 0; i < n; i++ {
if i < 3 {
fibMap[i] = i
} else {
fibMap[i] = fibMap[i-1] + fibMap[i-2]
  }
 }
return fibMap[n-1]
}

You can try with golang play ground

The Go Playground

Example interview question

https://leetcode.com/problems/climbing-stairs/