Fibonacci & Coin Change (Dynamic Programming)

In the previous lesson, we learned the difference between memoization and tabulation.

Now it is time to apply those ideas to real and classic Dynamic Programming problems.

In this lesson, we will focus on two famous problems: Fibonacci and Coin Change.

These problems appear frequently in interviews and exams because they clearly show why Dynamic Programming is needed.

Problem 1: Fibonacci Sequence

The Fibonacci sequence is defined as:

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

This definition looks simple, but implementing it efficiently is not trivial.

Why Naive Recursion Fails

A simple recursive solution recalculates the same values again and again.

For example, to compute F(5), the program calculates F(3) multiple times.

This leads to exponential time complexity and poor performance.

Fibonacci Using Memoization

Memoization stores results of already solved subproblems.

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

fib(10)

This solution avoids repeated calculations by remembering previous results.

Fibonacci Using Tabulation

Tabulation solves the problem from the bottom up.

def fib(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]

fib(10)

This approach is iterative, fast, and avoids recursion completely.

Problem 2: Coin Change

The Coin Change problem asks:

Given a set of coin values and a target amount, how many ways can we make that amount?

Example: Coins = [1, 2, 5]
Amount = 5

This problem involves overlapping subproblems, making it perfect for Dynamic Programming.

Understanding the Subproblem Structure

To form amount 5, we can:

• Use coin 1 and solve amount 4
• Use coin 2 and solve amount 3
• Use coin 5 and solve amount 0

Each smaller amount is reused multiple times.

Coin Change Using Tabulation

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

coin_change([1, 2, 5], 5)

Each dp[i] represents the number of ways to form amount i.

Why Order Matters in Coin Change

The order of loops is important.

Iterating coins first prevents counting duplicate combinations.

This small detail is a common interview trap.

Real-World Use Cases

Dynamic Programming problems like these appear in:

• Financial systems (change calculation)
• Resource allocation
• Path counting problems
• Scheduling systems

Mini Practice

Think carefully:

• Why is dp[0] initialized as 1?
• What happens if coin loops are reversed?

Exercises

Quick Quiz

Fibonacci and Coin Change teach the core idea of Dynamic Programming: solve once, reuse many times.

In the next lesson, we will study the Longest Common Subsequence (LCS) problem, a classic DP interview question.