Dynamic Programming Made Easy: Optimal Substructure Explained with Fibonacci Example

🚀 Understanding Dynamic Programming: Optimal Substructure with Real Code Example

When we talk about Dynamic Programming (DP), one of the key ideas is Optimal Substructure. This basically means:

👉 The solution of a big problem can be built by combining solutions of smaller problems.

{tocify} $title={Table of Contents}

To make this super clear, let’s look at a famous problem: the Fibonacci sequence.

Fibonacci numbers are defined like this:

• F(0) = 0
• F(1) = 1
• For any number n > 1, F(n) = F(n-1) + F(n-2)

So, if you want to find F(5), it’s basically:

F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)

See? Every number depends on the smaller numbers. That’s what we mean by optimal substructure.

Now, let’s check out the Python code and understand it step by step.

---

🖥️ The Code

# A simple recursive function to calculate Fibonacci numbers
def fibonacci(n):
    if n == 0:       # base case 1
        return 0
    elif n == 1:     # base case 2
        return 1
    else:            # recursive case
        return fibonacci(n - 1) + fibonacci(n - 2)

# Example: Finding Fibonacci of 6
print("Fibonacci of 6 is:", fibonacci(6))

---

🔎 Step-by-Step Explanation

1. Defining the Function

def fibonacci(n):

Here we are creating a function called fibonacci. It takes one input, n, which is the position in the Fibonacci series that we want to calculate.

For example:

• If n=6, it means we want the 6th Fibonacci number.

---

2. Base Cases

if n == 0:
    return 0
elif n == 1:
    return 1

These are stopping conditions.

• If someone asks for F(0), the answer is 0.
• If someone asks for F(1), the answer is 1.

Without base cases, the function would go into an infinite loop. Think of them like brakes in a car 🚗—they stop the recursion when needed.

---

3. Recursive Case

else:
    return fibonacci(n - 1) + fibonacci(n - 2)

This is the heart of the program.
If n is greater than 1, we don’t know the answer directly. Instead, we say:

👉 “The Fibonacci number at position n is the sum of the two previous Fibonacci numbers.”

For example, if n=6:

fibonacci(6) = fibonacci(5) + fibonacci(4)

The function will keep calling itself until it reaches the base cases (0 or 1).

This is exactly how optimal substructure works—breaking a big task into smaller ones.

---

4. Printing the Result

print("Fibonacci of 6 is:", fibonacci(6))

Here, we are asking Python: “Hey, give me the Fibonacci number at position 6.”

The answer is 8, because:

F(6) = F(5) + F(4)
     = (5) + (3)
     = 8

So the output will be:

Fibonacci of 6 is: 8

---

🧠 Why This Explains Optimal Substructure

Notice how we solved F(6) by solving smaller parts: F(5) and F(4).
And to solve those, we solved even smaller parts like F(3), F(2), etc.

This is a perfect example of optimal substructure:

• A big problem (finding F(6))
• Is broken down into smaller problems (F(5) and F(4))
• Which are again broken down until we reach the smallest problems (F(1) and F(0)), where we already know the answers.

---

⚡ Final Thoughts

• Dynamic Programming is powerful because it uses this optimal substructure property.
• Fibonacci is just one example, but this idea is used in shortest path algorithms, scheduling problems, resource optimization, and many more real-world problems.
• Once you understand this concept, DP problems will start feeling less scary and more like puzzles 🧩.