NUHMAN.com

Introduction

LeetCode 70: Climbing Stairs is a well-known dynamic programming problem that highlights a fundamental concept: optimal substructure. It's a twist on the Fibonacci sequence, and it's often used to teach recursion, memoization, and bottom-up DP.

The problem is intuitive and realistic—you need to figure out how many ways you can climb to the top of a staircase, taking either 1 or 2 steps at a time.

Problem Statement

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Examples:

go

Input: n = 2
Output: 2
// Explanation: 1 step + 1 step or 2 steps

Input: n = 3
Output: 3
// Explanation: 1+1+1, 1+2, 2+1

Constraints

• 1 <= n <= 45

Approach: Dynamic Programming (Bottom-Up)

This is essentially computing the nth Fibonacci number, with:

• ways[1] = 1
• ways[2] = 2
• ways[n] = ways[n-1] + ways[n-2] for n > 2

We can solve this:

1. Recursively with memoization (but not preferred in Go due to stack limits),
2. Bottom-up DP with an array, or
3. Optimized DP with just two variables.

We'll use the optimized DP approach, which uses O(1) space.

Go Implementation

go

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }

    first, second := 1, 2
    for i := 3; i <= n; i++ {
        first, second = second, first+second
    }

    return second
}

Explanation

• We initialize the base cases: 1 way to climb 1 step, 2 ways for 2 steps.
• Then we iteratively build up the solution from 3 to n.
• Each iteration only keeps the last two results, reducing space to O(1).

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• One pass from 3 to n.
• No array or recursion needed.

Alternative Approach: Recursive with Memoization

go

func climbStairs(n int) int {
    memo := make(map[int]int)
    return climb(n, memo)
}

func climb(n int, memo map[int]int) int {
    if n <= 2 {
        return n
    }
    if val, ok := memo[n]; ok {
        return val
    }
    memo[n] = climb(n-1, memo) + climb(n-2, memo)
    return memo[n]
}

Use this if you want a recursive approach that’s still efficient.

Conclusion

LeetCode 70 is a foundational DP problem that connects to real-world decision trees and optimization problems. It's great practice for interviews and introduces a reusable pattern you'll see again and again.

The optimized Go solution is short, fast, and shows the beauty of keeping things simple.