Where does the int result stop being exact in Go?

After 91 stairs. On a 64-bit platform int tops out at math.MaxInt, 9223372036854775807, and climbStairs(91) = 7540113804746346429 is the last answer below it. At 92 the addition wraps and the function hands back -6246583658587674878 instead of the real 12200160415121876738. Go does not panic on integer overflow, so either guard n before the loop or change the type. Moving to uint64 buys a single stair, since the answer for 93 is out of its range as well.

How do I return the exact count for huge n with math/big?

Return a *big.Int. Seed the pair with prev, curr := big.NewInt(1), big.NewInt(1) and advance it with prev, curr = curr, new(big.Int).Add(prev, curr). The fresh new(big.Int) is the important part: Add writes its result into the receiver, so curr.Add(prev, curr) would leave prev and curr pointing at the same value. Done this way, 100 stairs give 573147844013817084101 and 1000 stairs give a 209-digit number.

Why is ways declared with var before the closure is assigned?

With ways := func(i int) int { ... } the name ways is not in scope inside its own function literal, so a recursive call in the body fails to compile as undefined. Declaring var ways func(int) int on its own line first, then assigning the literal, lets the closure reach itself through the variable. A top-level function that takes the map as a parameter avoids the closure altogether.

Is a map or a slice the better memo in Go?

When the keys are exactly 0 to n, make([]int, n+1) is leaner: indexing is direct with no hashing, and because no real count is 0, the zero value can mean "not filled in yet", which removes the comma-ok check. The map[int]int in the solution is the general tool for sparse or unpredictable keys. In big-O terms they match, O(n) time and O(n) space.

How does the code change if a move can cover 1, 2 or 3 stairs?

Generalise the sum. Take the allowed moves as a []int, allocate ways := make([]int, n+1), seed ways[0] = 1, and for every stair i add ways[i-s] for each move s that does not overshoot (s <= i). Moves []int{1, 2, 3} give 7 routes up 4 stairs and 24 up 6, while passing []int{1, 2} brings back the counts from the solutions above.

Climbing Stairs Problem in Go (Golang): Recursion, Memo and DP

climb_stairs.go

Go 1.26

Not run yet

+ 7 hidden

Input

n = 4

Expected

The five sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.