Introduction to the Climbing Stairs Problem
The Climbing Stairs problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. The premise is deceptively simple: you are climbing a staircase that has n steps. At any point, you can either climb one step or two steps. The question is: how many distinct ways can you reach the top?
Despite its straightforward description, this problem is a gateway into understanding dynamic programming, recursion, memoization, and space-time tradeoffs. In this tutorial, we will explore multiple approaches to solving it in Go, analyze their complexities, and discuss best practices to help you write clean, idiomatic, and efficient code.
Why This Problem Matters
The Climbing Stairs problem matters because it teaches you how to recognize overlapping subproblems. Once you see that the number of ways to reach step n depends on the number of ways to reach steps n-1 and n-2, you have essentially rediscovered the Fibonacci sequence. This pattern appears in countless real-world scenarios, including:
- Resource allocation and budgeting problems
- Pathfinding on grids with restricted moves
- Combinatorial counting in game theory
- Optimization problems in finance and scheduling
Mastering this problem builds the foundation for tackling more complex dynamic programming challenges such as the Coin Change, House Robber, and Decode Ways problems.
Understanding the Problem Statement
Let us formalize the problem. Given a non-negative integer n representing the total number of steps, you need to return the number of distinct ways to climb from step 0 to step n. At each move, you may advance by either 1 or 2 steps.
For small values of n, we can enumerate the possibilities manually:
n = 1: 1 way → [1]n = 2: 2 ways → [1,1], [2]n = 3: 3 ways → [1,1,1], [1,2], [2,1]n = 4: 5 ways → [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]
Notice the pattern: 1, 2, 3, 5... This is the Fibonacci sequence shifted by one position. The recurrence relation is:
ways(n) = ways(n-1) + ways(n-2)
The intuition is that to reach step n, your last move was either a single step from n-1 or a double step from n-2. Summing the ways to reach those two previous steps gives the total ways to reach n.
Approach 1: Naive Recursion
The most direct translation of the recurrence relation is a recursive function. While elegant, this approach has exponential time complexity because it recomputes the same subproblems repeatedly.
package main
import "fmt"
func climbStairsNaive(n int) int {
if n <= 2 {
return n
}
return climbStairsNaive(n-1) + climbStairsNaive(n-2)
}
func main() {
fmt.Println(climbStairsNaive(5)) // Output: 8
}
This solution works for small inputs but becomes impractical for n greater than around 40 due to the exponential growth in recursive calls. The time complexity is O(2^n) and the space complexity is O(n) due to the call stack.
Approach 2: Top-Down Dynamic Programming with Memoization
To avoid recomputing subproblems, we can cache the results of each recursive call. This technique is called memoization and it transforms the exponential solution into a linear one.
package main
import "fmt"
func climbStairsMemo(n int) int {
memo := make(map[int]int)
return helper(n, memo)
}
func helper(n int, memo map[int]int) int {
if n <= 2 {
return n
}
if val, ok := memo[n]; ok {
return val
}
memo[n] = helper(n-1, memo) + helper(n-2, memo)
return memo[n]
}
func main() {
fmt.Println(climbStairsMemo(10)) // Output: 89
}
With memoization, each subproblem is computed only once. The time complexity drops to O(n), and the space complexity is O(n) for both the memo map and the recursion stack. This is a significant improvement and makes the solution practical for much larger inputs.
Approach 3: Bottom-Up Dynamic Programming
Instead of recursing from the top down, we can build the solution from the bottom up using an iterative loop. This eliminates the recursion stack entirely and is often preferred in production code.
package main
import "fmt"
func climbStairsDP(n int) int {
if n <= 2 {
return n
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
func main() {
fmt.Println(climbStairsDP(10)) // Output: 89
}
This approach has the same O(n) time complexity and O(n) space complexity, but it avoids recursion overhead. It is easier to reason about and debug, making it a solid choice for most scenarios.
Approach 4: Space-Optimized Solution
Looking closely at the bottom-up solution, you will notice that computing dp[i] only requires the values of dp[i-1] and dp[i-2]. We do not need to store the entire array. By keeping just two variables, we can reduce the space complexity to O(1).
package main
import "fmt"
func climbStairs(n int) int {
if n <= 2 {
return n
}
prev2, prev1 := 1, 2
for i := 3; i <= n; i++ {
current := prev1 + prev2
prev2 = prev1
prev1 = current
}
return prev1
}
func main() {
for i := 1; i <= 10; i++ {
fmt.Printf("n=%d => %d\n", i, climbStairs(i))
}
}
This is the optimal solution for the standard problem. It runs in O(n) time and uses O(1) space. For most interview settings, this is the answer you should aim to produce.
Handling Large Inputs and Overflow
One important consideration is that the Fibonacci sequence grows exponentially. For large values of n, the result will quickly exceed the capacity of a 64-bit integer. In Go, the int type is platform-dependent but typically 64 bits on modern systems. For n around 90, the result overflows int64.
If your application requires handling very large values of n, you should use the math/big package:
package main
import (
"fmt"
"math/big"
)
func climbStairsBig(n int) *big.Int {
if n <= 2 {
return big.NewInt(int64(n))
}
prev2 := big.NewInt(1)
prev1 := big.NewInt(2)
current := new(big.Int)
for i := 3; i <= n; i++ {
current.Add(prev1, prev2)
prev2.Set(prev1)
prev1.Set(current)
}
return prev1
}
func main() {
fmt.Println(climbStairsBig(100))
// Output: 573147844013817084101
}
Using big.Int allows you to compute results for arbitrarily large n without overflow, though at the cost of additional memory and computation time.
Best Practices
Choose the Right Approach for the Context
For interview settings, start with the naive recursive solution to demonstrate understanding, then optimize step by step. This shows your interviewer how you think about tradeoffs. In production code, prefer the space-optimized iterative solution unless you have a specific reason to use another approach.
Validate Inputs
Always consider edge cases. What happens if n is 0 or negative? Depending on the problem definition, you may want to return 0, 1, or return an error. Make your assumptions explicit:
func climbStairsSafe(n int) (int, error) {
if n < 0 {
return 0, fmt.Errorf("n must be non-negative, got %d", n)
}
if n <= 2 {
return n, nil
}
prev2, prev1 := 1, 2
for i := 3; i <= n; i++ {
prev2, prev1 = prev1, prev1+prev2
}
return prev1, nil
}
Write Idiomatic Go
Go encourages simplicity and clarity. Use short variable names in small scopes, leverage multiple assignment for swapping values, and avoid unnecessary abstractions. The space-optimized solution using prev2, prev1 = prev1, prev1+prev2 is a great example of idiomatic Go that is both concise and readable.
Add Tests
Always back your solution with tests. Here is a simple test suite using Go's built-in testing package:
package main
import "testing"
func TestClimbStairs(t *testing.T) {
tests := []struct {
input int
expected int
}{
{1, 1},
{2, 2},
{3, 3},
{4, 5},
{5, 8},
{10, 89},
{20, 10946},
}
for _, tt := range tests {
result := climbStairs(tt.input)
if result != tt.expected {
t.Errorf("climbStairs(%d) = %d; expected %d",
tt.input, result, tt.expected)
}
}
}
Run your tests with go test -v to ensure your implementation handles all expected cases correctly.
Conclusion
The Climbing Stairs problem is a perfect introduction to dynamic programming. By progressing from naive recursion to memoization, then to bottom-up iteration, and finally to a space-optimized solution, you learn how to systematically improve an algorithm's efficiency. In Go, the space-optimized approach using two variables and tuple assignment is both elegant and performant, running in O(n) time with O(1) space. Remember to consider edge cases, validate inputs, and write tests to ensure correctness. Once you internalize the patterns in this problem, you will be well-equipped to tackle a wide range of dynamic programming challenges with confidence.