DP: Fibonacci and Staircase Problems

Mastering dynamic programming (DP) often begins with seemingly simple counting problems like generating Fibonacci numbers or calculating ways to climb stairs. These problems are the perfect sandbox for understanding the core DP paradigm: breaking a complex problem into overlapping subproblems, solving each just once, and storing their results to build up to a final answer. By learning to transform an intuitive but exponentially slow recursive solution into an efficient O(n) one—and then optimizing further—you build the fundamental intuition needed to tackle far more complex DP challenges in algorithm design and optimization.

From Recursive Intuition to DP Formulation

The classic Fibonacci sequence, where each number is the sum of the two preceding ones ($F(n)=F(n-1)+F(n-2)$ with $F(0)=0,F(1)=1$), provides a crystal-clear view of the problem DP solves. The natural recursive solution directly mirrors the mathematical definition.

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

While beautifully simple, this function suffers from exponential time complexity $O(2^n)$. The reason is overlapping subproblems: to compute fib_recursive(5), you compute fib_recursive(3) multiple times independently. This massive redundancy is the inefficiency DP eliminates. The key insight is that there are only n+1 distinct subproblems (fib(0), fib(1), ..., fib(n)). Solving and storing each one just once is the heart of the dynamic programming approach.

Implementing DP: Memoization and Tabulation

There are two primary techniques to implement DP: top-down memoization and bottom-up tabulation. Both have the same goal—avoiding recomputation—but differ in their approach.

Memoization is essentially the recursive solution enhanced with a lookup table (often a dictionary or array). Before making a recursive call, you check if the result for that subproblem is already stored. If it is, you return it instantly; if not, you compute it recursively, store it, and then return it. This approach is "top-down" because you start with the problem you want (fib(n)) and recursively break it down.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Tabulation, in contrast, is iterative and "bottom-up." You explicitly solve all subproblems in a systematic order, starting from the smallest (base cases) and building up to the desired n. You use a table (typically an array dp) where dp[i] stores the answer to the subproblem fib(i).

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Both methods reduce the time complexity to $O(n)$, as each subproblem is computed once. The memoization stack has $O(n)$ space overhead, while tabulation uses $O(n)$ array space.

The Staircase Climbing Problem

The staircase problem is a direct and powerful generalization of the Fibonacci logic. The problem is: "You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 step or 2 steps. In how many distinct ways can you climb to the top?"

Let ways(i) represent the number of distinct ways to reach step i. To get to step i, your last move was either a 1-step jump from step i-1 or a 2-step jump from step i-2. Therefore, the number of ways to get to i is the sum of the ways to get to i-1 and i-2. This gives us the recurrence relation: $$ways(i)=ways(i-1)+ways(i-2)$$

The base cases are: ways(0) = 1 (one way to be on the ground), and ways(1) = 1 (only the 1-step path). Notice this generates the sequence: 1, 1, 2, 3, 5, 8... which is essentially the Fibonacci sequence shifted. The tabulation solution is structurally identical to the Fibonacci dp solution, differing only in base case initialization.

def climb_stairs(n):
    if n <= 1:
        return 1
    dp = [0] * (n+1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Space Optimization and Problem Generalization

In both the Fibonacci and staircase problems, you only need the last two computed values to find the next one. You don't need to keep the entire dp array. This allows for space optimization from $O(n)$ to $O(1)$. You can replace the array with two or three variables that you update iteratively.

def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1  # F(0), F(1)
    for _ in range(2, n+1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1

This optimization is a critical step in DP problem-solving: asking, "Do I need the entire history, or just the most recent subproblem results?"

The staircase problem can be generalized further, for example, to the tiling problem: "Given a 2 x n board and tiles of size 2 x 1, count the number of ways to tile the board." A tile can be placed vertically (covering one column) or two tiles can be placed horizontally (covering two columns). The recurrence is identical: tile(n) = tile(n-1) + tile(n-2). Recognizing this structural equivalence—where the recurrence and overlapping subproblems pattern match a known problem—is the DP problem-solving intuition you are building.

Common Pitfalls

Misunderstanding the Nature of Overlapping Subproblems: The biggest mistake is applying DP where it isn't needed. DP is optimal only when the problem has the optimal substructure (an optimal solution can be constructed from optimal solutions of its subproblems) and overlapping subproblems. Problems like merge sort have optimal substructure but no overlapping subproblems, so divide-and-conquer is suitable, not DP. Always ask: "Will I be solving the exact same subproblem multiple times?"

Inefficient Space Usage in Simple Recurrences: As shown, for recurrences like dp[i] = dp[i-1] + dp[i-2], storing the full dp array is wasteful. Failing to recognize the opportunity for $O(1)$ space optimization is a common oversight. Before finalizing a solution, always review the recurrence to see if you can "compress" the state.

Incorrect Base Case Initialization: A subtle but critical error. In the staircase problem, defining ways(0)=1 is logical but not always intuitively obvious. Some mistakenly start with dp[1]=1, dp[2]=2. While this might work for some n, it's fragile. Always derive base cases from the smallest, physically meaningful instance of the problem and validate them manually.

Confusing Memoization with Basic Recursion: Simply adding a global counter to a recursive function doesn't make it memoized. Memoization requires a lookup data structure that is persistently referenced across recursive calls. A common error is re-initializing the memo dictionary inside the recursive function on every call, which defeats its purpose.

Summary

• Dynamic programming efficiently solves problems with overlapping subproblems by storing the results of solved subproblems to avoid recomputation, transforming exponential-time recursive solutions into polynomial-time ones.
• The two main DP implementation strategies are top-down memoization (recursive with caching) and bottom-up tabulation (iterative table-filling). Both achieve $O(n)$ time for Fibonacci-type problems, with tabulation often having a slight advantage by avoiding recursion overhead.
• The staircase climbing problem is a canonical DP exercise with a recurrence (ways(i) = ways(i-1) + ways(i-2)) identical in structure to the Fibonacci sequence, demonstrating how a simple change in framing creates a new problem solvable with the same pattern.
• When the recurrence depends only on a constant number of previous states (e.g., the last two), you can optimize space from $O(n)$ to $O(1)$ by replacing the full DP table with a few variables, a crucial step for writing efficient DP code.
• Building DP intuition involves recognizing these fundamental patterns—like the Fibonacci recurrence—in new problem contexts, such as tiling or other counting problems, which allows you to rapidly identify when a dynamic programming approach is applicable.