dynamic_programming.go

package main

import (
	"fmt"
	"sort"
)

func main() {
	cache := make(map[int]int)
	for i := 1; i < 50; i++ {
		fib(i, cache)
	}

	keys := []int{}
	for k := range cache {
		keys = append(keys, k)
	}

	sort.Ints(keys)

	for k := range keys {
		fmt.Printf("%d:%d\n", k, cache[k])
	}
}

func fib(n int, cache map[int]int) int {
	if n < 2 {
		return n
	}
	if cache[n] == 0 {
		cache[n] = fib(n-1, cache) + fib(n-2, cache)
	}
	return cache[n]
}