Understanding Fibonacci: An Easy Introduction to Dynamic Programming

---

Welcome, future coding master! You've just stumbled upon one of the most powerful tools in a programmer's arsenal: Dynamic Programming (DP). It sounds intimidating, right? Like it's reserved for wizards in high towers. But what if I told you it's just about being smart and a little lazy—solving a problem once and remembering the answer forever?

Today, we'll conquer our first DP pattern, the one that all others are built upon, using the simple, elegant idea behind the Fibonacci sequence. We'll see how this one pattern can help us solve a variety of problems, from counting rabbit generations to finding the cheapest way up a staircase. Let's start our climb!

---

The Core Idea: The Fibonacci Sequence 🐇

Imagine you have a pair of newborn rabbits. After one month, they mature. After a second month, they produce a new pair. This pattern continues, with each mature pair producing a new pair every month. The number of rabbit pairs you have each month follows this sequence:

1, 1, 2, 3, 5, 8, 13, ...

This is the famous Fibonacci sequence. Each number is the sum of the two preceding ones. Mathematically, we write it as:

F(n)=F(n−1)+F(n−2)

This simple recurrence is the key. Let's see how we can code it.

The Naive Recursive Way

The most direct translation of the formula is a recursive function.

Java

public int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

This works, but it's incredibly slow for larger numbers. Why? It recalculates the same values over and over again. For fib(5), it calculates fib(3) twice, fib(2) three times, and so on. This is where DP comes to the rescue.

The Optimal Solution: The Bottom-Up Approach

Instead of starting from the top (n) and going down, let's start from the bottom (0) and build our way up. We only ever need the last two numbers to calculate the next one.

This is the essence of bottom-up DP: solve the smallest sub-problems first and use their results to build up to the final answer.

Java

// Fibonacci Number - LeetCode 509
public int fib(int n) {
    if (n <= 1) {
        return n;
    }

    // We only need two variables to store the previous two results
    int prev2 = 0; // Represents F(n-2)
    int prev1 = 1; // Represents F(n-1)
    int current = 0;

    // Build up from 2 to n
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1; // prev1 holds the final result
}

Complexity:

• Time: O(n) - We just loop through the numbers once.

• Space: O(1) - We only use a few variables, no matter how big n is!

---

Problem 1: Climbing Stairs 🧗‍♀️

The Challenge: 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?

Think about how you could get to the n-th step. You must have come from either the (n-1)-th step (by taking one step) or the (n-2)-th step (by taking two steps).

So, the total number of ways to reach step n is:

ways(n) = ways(n-1) + ways(n-2)

Wait a minute... that's the Fibonacci formula! Reaching step 1 has 1 way. Reaching step 2 has 2 ways (1+1 or 2). The sequence of ways is 1, 2, 3, 5, ..., which is just the Fibonacci sequence shifted a bit.

The Optimal Solution

Since the pattern is identical, the code is almost the same. We just change our base cases to match the problem.

Java

// Climbing Stairs - LeetCode 70
public int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }

    // We only need the number of ways for the previous two steps
    int two_steps_back = 1; // Ways to reach step n-2 (base case for step 1)
    int one_step_back = 2;  // Ways to reach step n-1 (base case for step 2)
    int all_ways = 0;

    // Start building from step 3
    for (int i = 3; i <= n; i++) {
        all_ways = one_step_back + two_steps_back;
        two_steps_back = one_step_back;
        one_step_back = all_ways;
    }
    return one_step_back; // This variable now holds the ways for step n
}

By recognizing the underlying Fibonacci pattern, we solved a new problem with the same elegant, efficient solution.

---

Problem 2: Min Cost Climbing Stairs 💰

The Challenge: You are given an integer array cost where cost[i] is the cost of the i-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You can start from either step 0 or step 1. Return the minimum cost to reach the top of the floor.

This is a twist! We're not counting ways anymore; we're minimizing cost. But the core logic remains.

To find the minimum cost to reach step i, you must have come from either step i-1 or step i-2. You'd obviously choose the path that cost less up to that point.

So, the minimum cost to arrive at step i is:

min_cost(i) = cost[i] + min(min_cost(i-1), min_cost(i-2))

The "top" is considered one step past the end of the array. So, our final answer will be the minimum of reaching the last two steps, since we can take 1 or 2 steps from them to get to the top.

The Optimal Solution

Let's use our bottom-up approach again. We can modify the input array cost itself to store the minimum cost to reach each step. This is called solving it in-place and saves space.

Java

// Min Cost Climbing Stairs - LeetCode 746
public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;

    // Start from the third step and update the cost array
    // cost[i] will store the minimum cost to reach step i
    for (int i = 2; i < n; i++) {
        cost[i] += Math.min(cost[i - 1], cost[i - 2]);
    }

    // The final answer is the minimum cost of reaching the last two steps,
    // as we can jump from either to the "top"
    return Math.min(cost[n - 1], cost[n - 2]);
}

Wait, we can do even better! Just like before, we only need the costs of the previous two steps. We don't need to modify the array.

Java

// Space-Optimized Solution
public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int first = cost[0]; // Min cost to reach step 0
    int second = cost[1]; // Min cost to reach step 1

    for (int i = 2; i < n; i++) {
        int current = cost[i] + Math.min(first, second);
        first = second;
        second = current;
    }

    return Math.min(first, second);
}

Complexity:

• Time: O(n) - A single pass through the array.

• Space: O(1) - Constant space for our variables.

---

Your First Summit 🏔️

Congratulations! You've successfully navigated your first Dynamic Programming pattern. You saw how a single, simple idea—building solutions from the bottom up and remembering previous results—can solve multiple problems efficiently.

The Key Takeaway:

When you see a problem that can be broken down into smaller, overlapping versions of itself (like reaching step n depends on reaching n-1 and n-2), you've found a candidate for DP!

This is just the base camp. Many more patterns and exciting climbs await you on your Dynamic Programming journey. Keep climbing!