Dynamic Programming Made Easy: Optimal Substructure Explained with Fibonacci Example

byMD Modasshar hussain -
0

🚀 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.

Dynamic Programming Made Easy: Optimal Substructure Explained with Fibonacci Example

{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 🧩.


 

 Algorithm



Learn algorithms with examples and step-by-step explanations

☁️ Cloud Computing
🤖 Artificial Intelligence (AI)
📊 Data Analyst


🧠 Machine Learning (ML)
🗄️ SQL
💠 C++ Programming


🐍 Python
🌐 Web Development
🚀 Tech to Know & Technology


Tags

You may like these posts

Post a Comment

Ask any query by comments

Previous Post Next Post