Fibonacci & Climbing Stairs

Fibonacci and Climbing Stairs are the gateway to 1D dynamic programming. Both use the same recurrence—each step depends on the previous one or two results. This lesson covers the theory, tabulation traces, and full implementations in C, Java, and Python with output explanation tables.

Overview

These problems teach the same DP pattern:

State:     dp[i] = answer for subproblem of size i
Recurrence: dp[i] = dp[i-1] + dp[i-2]   (or min/max variant)
Base:      dp[0], dp[1] known
Goal:      dp[n]

Fibonacci Problem

Compute the n-th Fibonacci number where F(0)=0, F(1)=1, and F(n)=F(n−1)+F(n−2).

DP state: dp[i] = Fibonacci number at index i.

Why DP? Naive recursion recomputes F(2), F(3), … many times. Storing each value once reduces time from O(2ⁿ) to O(n).

Fibonacci Code (C, Java, Python)

Bottom-up tabulation with O(1) space—preferred for interviews and production.

Python

def fibonacci(n: int) -> int:
    """Return n-th Fibonacci number — bottom-up DP, O(n) time, O(1) space."""
    # Base cases: F(0) = 0, F(1) = 1
    if n <= 1:
        return n

    # Rolling window: prev2 = F(i-2), prev1 = F(i-1)
    prev2, prev1 = 0, 1

    for _ in range(2, n + 1):
        curr = prev1 + prev2           # F(i) = F(i-1) + F(i-2)
        prev2, prev1 = prev1, curr     # slide window forward

    return prev1                       # F(n)


if __name__ == "__main__":
    # Demo output for sample inputs
    for n in [0, 1, 5, 8, 10]:
        print(f"fib({n}) = {fibonacci(n)}")

Java

public class Fibonacci {

    /**
     * Bottom-up Fibonacci with O(1) extra space.
     * prev2 = F(i-2), prev1 = F(i-1)
     */
    public static int fibonacci(int n) {
        // Base cases
        if (n <= 1) return n;

        int prev2 = 0;  // F(0)
        int prev1 = 1;  // F(1)

        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;  // F(i) = F(i-1) + F(i-2)
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;  // F(n)
    }

    public static void main(String[] args) {
        int[] tests = {0, 1, 5, 8, 10};
        for (int n : tests) {
            System.out.println("fib(" + n + ") = " + fibonacci(n));
        }
    }
}

C

#include <stdio.h>

/* Bottom-up Fibonacci: O(n) time, O(1) space */
int fibonacci(int n) {
    if (n <= 1) return n;  /* base cases F(0), F(1) */

    int prev2 = 0;  /* F(i-2) */
    int prev1 = 1;  /* F(i-1) */
    int curr, i;

    for (i = 2; i <= n; i++) {
        curr = prev1 + prev2;  /* F(i) = F(i-1) + F(i-2) */
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main(void) {
    int tests[] = {0, 1, 5, 8, 10};
    int i, n, len = sizeof(tests) / sizeof(tests[0]);

    for (i = 0; i < len; i++) {
        n = tests[i];
        printf("fib(%d) = %d\n", n, fibonacci(n));
    }
    return 0;
}

Fibonacci Output & Trace Tables

Program output (all three languages)

Input → output reference

DP table trace for n = 6 (full tabulation view)

Climbing Stairs Problem

You can climb 1 or 2 steps at a time. How many distinct ways to reach the top of n steps?

DP state: dp[i] = number of ways to reach step i.

Recurrence: To reach step i, you came from step i−1 (1-step) or i−2 (2-step):

dp[i] = dp[i-1] + dp[i-2]
dp[1] = 1,  dp[2] = 2

Climbing Stairs Code (C, Java, Python)

Python

def climb_stairs(n: int) -> int:
    """Count ways to climb n steps (1 or 2 at a time). Same pattern as Fibonacci."""
    # Base: 1 step → 1 way, 2 steps → 2 ways
    if n <= 2:
        return n

    prev2, prev1 = 1, 2  # ways(1), ways(2)

    for _ in range(3, n + 1):
        curr = prev1 + prev2       # ways(i) = ways(i-1) + ways(i-2)
        prev2, prev1 = prev1, curr

    return prev1


if __name__ == "__main__":
    for n in [1, 2, 3, 4, 5, 6]:
        print(f"ways({n}) = {climb_stairs(n)}")

Java

public class ClimbingStairs {

    /** LeetCode 70 — distinct ways to climb n steps (1 or 2 each move). */
    public static int climbStairs(int n) {
        if (n <= 2) return n;  // base cases

        int prev2 = 1;  // ways to reach step 1
        int prev1 = 2;  // ways to reach step 2

        for (int i = 3; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    public static void main(String[] args) {
        for (int n = 1; n <= 6; n++) {
            System.out.println("ways(" + n + ") = " + climbStairs(n));
        }
    }
}

C

#include <stdio.h>

/* Climbing stairs — ways(n) = ways(n-1) + ways(n-2) */
int climb_stairs(int n) {
    if (n <= 2) return n;

    int prev2 = 1;  /* ways(1) */
    int prev1 = 2;  /* ways(2) */
    int curr, i;

    for (i = 3; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main(void) {
    int n;
    for (n = 1; n <= 6; n++) {
        printf("ways(%d) = %d\n", n, climb_stairs(n));
    }
    return 0;
}

Climbing Stairs Output & Trace Tables

Program output (all three languages)

Input → output with valid paths

DP table trace for n = 5

Min Cost Climbing Stairs

LeetCode 746: Each step has a cost; you may start at index 0 or 1 and pay to leave a step. Find minimum cost to reach the top (beyond last index).

Recurrence: dp[i] = cost[i] + min(dp[i−1], dp[i−2])

Python

def min_cost_climbing_stairs(cost):
    """LeetCode 746 — min cost to reach top; can start at step 0 or 1."""
    n = len(cost)
    prev2, prev1 = cost[0], cost[1]  # min cost to leave step 0 and 1

    for i in range(2, n):
        # Pay cost[i] plus cheaper path from previous two steps
        curr = cost[i] + min(prev1, prev2)
        prev2, prev1 = prev1, curr

    # Jump to top from either last step (no extra cost)
    return min(prev1, prev2)


# Demo: cost = [10, 15, 20] → output 15
print(min_cost_climbing_stairs([10, 15, 20]))

Java

public class MinCostStairs {

    /** Min cost to reach top — start at index 0 or 1, pay to leave each step. */
    public static int minCostClimbingStairs(int[] cost) {
        int prev2 = cost[0];
        int prev1 = cost[1];

        for (int i = 2; i < cost.length; i++) {
            int curr = cost[i] + Math.min(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }
        // Final hop to top costs nothing extra
        return Math.min(prev1, prev2);
    }

    public static void main(String[] args) {
        int[] cost = {10, 15, 20};
        System.out.println(minCostClimbingStairs(cost));  // 15
    }
}

C

#include <stdio.h>

/* Min cost climbing stairs — O(n) time, O(1) space */
int min_cost(int cost[], int n) {
    int prev2 = cost[0];
    int prev1 = cost[1];
    int curr, i;

    for (i = 2; i < n; i++) {
        curr = cost[i] + (prev1 < prev2 ? prev1 : prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1 < prev2 ? prev1 : prev2;  /* cheapest finish */
}

int main(void) {
    int cost[] = {10, 15, 20};
    printf("%d\n", min_cost(cost, 3));  /* output: 15 */
    return 0;
}

Min cost output & trace — cost = [10, 15, 20]

More Examples

Example 1: Tribonacci (3-term recurrence)

T(n) = T(n−1) + T(n−2) + T(n−3). Same 1D DP pattern with three rolling variables.

Example 2: Climbing stairs with step sizes {1, 2, 3}

Recurrence becomes dp[i] = dp[i−1] + dp[i−2] + dp[i−3].

Example 3: Decode Ways (same 1D structure)

String decoding counts valid splits—still linear DP: dp[i] depends on previous one or two positions. See coin change and string DP topics next in the series.

Example 4: Naive vs DP runtime (Fibonacci n = 30)

Approach Comparison

Real-Life Applications

Fibonacci and climbing-stairs DP count linear sequences of choices where each step depends on the previous one or two outcomes—growth, paths, and costs in the real world follow the same recurrence.

Interview Tips

1. State the recurrence and base cases before coding.
2. Mention naive O(2ⁿ) first, then fix with DP.
3. For climbing stairs, note it equals shifted Fibonacci.
4. Offer O(1) space optimization with two (or three) variables.
5. Trace n=4 or n=5 on the whiteboard using a small table.
6. Know min-cost variant — same pattern, min instead of sum.