package main import "fmt" // global variable used to store base cases var BaseCases = make(map[uint]uint) // cannot use := outside function body func StepsBruteForce (n uint) uint { if val, ok := BaseCases[n]; ok { // Two statement if: assignment; condition return val } else { return StepsBruteForce(n-1) + StepsBruteForce(n-2) + StepsBruteForce(n-3) } } func StepsMemo (n uint) uint { var memo []uint = make([]uint, n+1) for i := uint(0); i <= n; i++ { memo[i] = 0 } return StepsMemoRec(n, &memo) } func StepsMemoRec (n uint, memo *[]uint) uint { if (*memo)[n] != 0 { // already computed return (*memo)[n] } if val, ok := BaseCases[n]; ok { return val } else { (*memo)[n] = StepsMemoRec(n-1, memo) + StepsMemoRec(n-2, memo) + StepsMemoRec(n-3, memo) return (*memo)[n] } } func StepsDP (n uint) uint { DPtable := make([]uint, n+1) DPtable[1] = BaseCases[1] DPtable[2] = BaseCases[2] DPtable[3] = BaseCases[3] for i := uint(4); i <= n; i++ { DPtable[i] = DPtable[i-1] + DPtable[i-2] + DPtable[i-3] } return DPtable[n] } func main () { BaseCases[1] = 1 // {1} BaseCases[2] = 2 // {1+1, 2} BaseCases[3] = 4 // {1+1+1, 1+2, 2+1, 3} var n uint = 15 fmt.Println(StepsBruteForce(n)) fmt.Println(StepsMemo(n)) fmt.Println(StepsDP(n)) }