Staircase Problem

staircase.go

package main

import (
	"fmt"
	"math/big"
)

var memo = map[int]*big.Int{
	0: big.NewInt(0),
	1: big.NewInt(1),
	2: big.NewInt(2),
	3: big.NewInt(4),
}

func nWays(n int) *big.Int {
	if n <= 0 {
		return big.NewInt(0)
	}
	v, ok := memo[n]
	if ok {
		return v
	}
	sum := big.NewInt(0)
	sum.Add(sum, nWays(n-1))
	sum.Add(sum, nWays(n-2))
	sum.Add(sum, nWays(n-3))
	memo[n] = sum
	return sum
}

func displayMemo() {
	for i := 0; i < len(memo); i++ {
		fmt.Printf("f(%d) = %d\n", i, memo[i])
	}
}

func main() {
	n := 1000
	nWays(n)
	displayMemo()
}

https://play.golang.org/p/5OZjwgxyM7v