Overlapping Subproblems and Optimal Substructure in DSA C - Build from Scratch

Understanding Overlapping Subproblems and Optimal Substructure with Fibonacci

📖 Scenario: Imagine you want to find the number of ways to climb stairs where you can take 1 or 2 steps at a time. This problem can be solved using the Fibonacci sequence, which shows overlapping subproblems and optimal substructure.

🎯 Goal: Build a program that calculates the 10th Fibonacci number using a simple recursive function and then optimize it using memoization to avoid repeated calculations.

📋 What You'll Learn

Create an integer array called memo to store intermediate Fibonacci results

Write a recursive function fib that calculates Fibonacci numbers

Use memoization to store and reuse results of subproblems

Print the 10th Fibonacci number

💡 Why This Matters

🌍 Real World

Many problems like route planning, resource allocation, and sequence analysis use overlapping subproblems and optimal substructure to find efficient solutions.

💼 Career

Understanding these concepts is key for software engineers working on optimization, algorithms, and performance-critical applications.

1

Create a recursive Fibonacci function

Write a recursive function called fib that takes an integer n and returns the nth Fibonacci number using the formula: fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1.

DSA C

#include 

// Write the recursive fib function here

int main() {
    return 0;
}

Hint

Use simple if statements for base cases and recursive calls for others.

2

Add memoization array

Create a global integer array called memo of size 11 and initialize all elements to -1 to store Fibonacci results for numbers 0 to 10.

DSA C

#include 

int memo[11];

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

int main() {
    // Initialize memo array to -1
    // Your code here
    return 0;
}

Hint

Use a for loop to set each element of memo to -1.

3

Modify fib function to use memoization

Modify the fib function to check if memo[n] is not -1 and return it if so. Otherwise, calculate fib(n) recursively, store the result in memo[n], and return it.

DSA C

#include 

int memo[11];

int fib(int n) {
    // Check if result is already computed
    // Your code here

    if (n == 0) return 0;
    if (n == 1) return 1;

    // Compute and store result
    // Your code here
}

int main() {
    for (int i = 0; i < 11; i++) {
        memo[i] = -1;
    }
    return 0;
}

Hint

Use memo[n] to save and reuse results.

4

Print the 10th Fibonacci number

In the main function, call fib(10) and print the result using printf with the format "%d\n".

DSA C

#include 

int memo[11];

int fib(int n) {
    if (memo[n] != -1) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    for (int i = 0; i < 11; i++) {
        memo[i] = -1;
    }
    // Print the 10th Fibonacci number
    // Your code here
    return 0;
}

Hint

Use printf("%d\n", fib(10)); to print the result.