Bottom-up DP: Fibonacci & stairs

Overview

Dynamic programming is what you reach for when a recursive solution keeps solving the same subproblem over and over. Naive fib(n) re-derives fib(n-2) an exponential number of times; the fix is to compute each subproblem once and reuse the answer. There are two ways to do that — memoization caches results as the recursion unwinds (top-down), and tabulation fills a table from the base cases upward (bottom-up). Fibonacci and the stair-climbing count are the same recurrence with different base cases, and both collapse to two running variables once you notice each step only needs the previous two.

Why it matters

The exponential-to-linear jump is not a micro-optimisation: naive fib(50) performs about 2.5 billion calls, while the DP version does 50 additions. Recognising overlapping subproblems is the skill that turns an intractable brute force into something that runs instantly, and it is the foundation every later lesson in this track builds on.

Core concepts

The two DP preconditions. A problem is a DP candidate when it has overlapping subproblems (the same smaller instance is needed repeatedly) and optimal substructure (an optimal answer is built from optimal answers to subproblems). Missing either one and DP does not apply — divide-and-conquer like merge sort has optimal substructure but no overlap, so caching buys nothing.

Top-down memoization. Keep the natural recursion, add a cache: check it on entry, store before returning. Easy to derive from a brute force, but pays call-stack and lookup overhead and can overflow the stack for deep recurrences.

Bottom-up tabulation. Identify the dependency order, then fill a table from the base cases forward. No recursion, no stack risk, and usually faster — the style used throughout this track.

Rolling variables. When dp[i] depends only on a fixed window of earlier entries, the table itself is unnecessary. Fibonacci needs dp[i-1] and dp[i-2], so two long long variables replace an array — O(1) space.

Base cases decide everything. fib starts 0, 1; stairs start 1, 1 (one way to stand still, one way to climb one step). Identical recurrence, different seeds, different answers — get the base cases wrong and every value after them is wrong.

Syntax notes

/* bottom-up, O(n) time, O(1) space */
long long fib(int n) {
    if (n < 2) return n;                 // base cases: fib(0)=0, fib(1)=1
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;             // dp[i] = dp[i-1] + dp[i-2]
        a = b; b = c;                    // roll the window forward
    }
    return b;
}

/* same recurrence, different base cases */
long long climb(int n) {
    long long a = 1, b = 1;              // 1 way to climb 0 steps, 1 way to climb 1
    for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }
    return b;
}

Key points:

• long long — fib(47) already exceeds a 32-bit int.
• The rolling pair replaces an array entirely; no allocation, no free.
• Handle n < 2 before the loop, or the seeds are never returned.

Lesson

Naive recursion for Fibonacci recomputes the same subproblems exponentially many times. Dynamic programming stores each subresult once and reuses it, turning O(2^n) into O(n). Fibonacci needs only two rolling variables; counting ways to climb stairs is the same recurrence with different base cases.

Code examples

#include <stdio.h>
/* Bottom-up beats naive recursion: O(n) with two rolling variables. */
static long long fib(int n){ if(n<2) return n; long long a=0,b=1; for(int i=2;i<=n;i++){ long long c=a+b; a=b; b=c; } return b; }
static long long climb(int n){ long long a=1,b=1; for(int i=2;i<=n;i++){ long long c=a+b; a=b; b=c; } return b; }
int main(void){
    printf("fib(0..10):");
    for(int i=0;i<=10;i++) printf(" %lld", fib(i));
    putchar('\n');
    printf("ways to climb 5 stairs (1 or 2 at a time) = %lld\n", climb(5));
    return 0;
}

Line by line

Common mistakes

Writing the naive recursion and expecting it to scale; wrong base cases for the stairs count.

Debugging tips

Compiler errors and warnings:

• warning: integer overflow in expression — you used int for a value that outgrows it. Use long long.
• -Wreturn-type if a branch of the recursion forgets to return.

Runtime symptoms:

• Correct for small n, wrong from around 47 upward. Signed overflow in int. fib(46) is 1,836,311,903 — the next one overflows.
• The answer is off by one position. Base cases. Print fib(0), fib(1), fib(2) first; if fib(2) is not 1, the seeds are wrong.
• Stack overflow / very slow. You kept the naive recursion with no cache. Confirm the memo is actually being read, not just written.
• Stairs and Fibonacci disagree. That is expected — same recurrence, different base cases (climb(2) is 2, fib(2) is 1).

Technique: print the first ten values of any new DP before trusting it. A recurrence that is right from index 0 to 9 is almost always right everywhere.

Memory safety

• Integer overflow is the real hazard here. Signed overflow is undefined behaviour in C, not a wrap. Fibonacci and counting DPs grow fast, so size the accumulator deliberately (long long, or a modulus if the problem specifies one).
• No allocation in the rolling version. That is a feature: with two scalars there is nothing to leak, nothing to free, and no failure path to handle.
• If you tabulate with an array, malloc((n+1) * sizeof *dp) must check the return for NULL, and n must be validated first — a negative or huge n makes the size computation wrap and under-allocate.
• Recursion depth. A top-down memo on n = 1,000,000 will overflow the call stack long before it runs out of heap. Bottom-up has no such limit.

Real-world uses

Concrete uses: The overlapping-subproblems pattern underlies diff tools, spell checkers, sequence alignment in bioinformatics, and query planners that reuse cost estimates for repeated sub-plans. The specific Fibonacci-shaped recurrence appears in counting problems: tilings, valid string constructions, and the stair-climbing family of interview questions. Rolling-window DP is how embedded code runs filters in constant memory.

Professional best practices:

Beginner:

• Write the recurrence and base cases in a comment before you write the loop.
• Verify the first few values by hand.

Intermediate:

• Prefer bottom-up when the dependency order is obvious; it avoids stack limits and is usually faster.
• Reduce the table to a rolling window whenever dp[i] depends only on a fixed number of predecessors — it turns O(n) space into O(1).
• Choose the accumulator type from the growth rate of the answer, not from habit.

Practice tasks

1. (Beginner) Iterative Fibonacci. Implement long long fib(int n) with the rolling pair. Requirements: handle n = 0 and n = 1; use long long. Example: fib(10) → 55; fib(50) → 12586269025. Concepts: base cases, rolling window.

2. (Beginner) Climbing stairs. Implement long long climb(int n) where you may take 1 or 2 steps. Example: climb(4) → 5. Concepts: same recurrence, different seeds.

3. (Intermediate) Memo vs table. Solve fib both top-down with an array memo and bottom-up, and confirm they agree for n in 0..90. Concepts: the two DP styles.

4. (Intermediate) Generalised steps. Count the ways to climb n stairs taking 1, 2 or 3 steps at a time. Hint: the window is now three values wide. Example: n = 4 → 7. Concepts: widening the recurrence.

Summary

Dynamic programming applies when a problem has overlapping subproblems and optimal substructure — then computing each subproblem once turns exponential work into linear. Memoization caches a natural recursion top-down; tabulation fills a table bottom-up from the base cases and avoids stack limits. When each entry depends only on a fixed window of earlier ones, drop the table entirely and roll a couple of variables, as Fibonacci and stair-climbing both do. Get the base cases right — they and the recurrence are the whole algorithm — and pick an accumulator wide enough that the answer cannot overflow.

Practice with these exercises

• Fibonacci (bottom-up)
• Climbing stairs