Overlapping Subproblems and Optimal Substructure in DSA C

Mental Model

Some problems can be broken into smaller parts that repeat, and the best solution uses the best answers to these parts.

Analogy: Imagine building a big Lego castle by reusing smaller Lego sections you already built instead of making them again each time.

Problem
  ↓
Subproblem A -> Subproblem B -> Subproblem C
  ↑           ↓
  ← Subproblem A (reused)

Best solution = best answers to subproblems combined

Dry Run Walkthrough

Input: Calculate Fibonacci number for 4 (fib(4))

Goal: Show how fib(4) calculation reuses fib(2) and fib(3) results to avoid repeated work

Step 1: Calculate fib(4) by calculating fib(3) and fib(2)

fib(4) -> fib(3), fib(2)

Why: fib(4) depends on fib(3) and fib(2) to get the answer

Step 2: Calculate fib(3) by calculating fib(2) and fib(1)

fib(4) -> fib(3) -> fib(2), fib(1); fib(2)

Why: fib(3) depends on fib(2) and fib(1), fib(2) is needed again

Step 3: Reuse fib(2) result instead of recalculating

fib(4) -> fib(3) -> fib(2) [reused], fib(1); fib(2) [reused]

Why: fib(2) is an overlapping subproblem, so reuse saves work

Step 4: Combine fib(3) and fib(2) results to get fib(4)

fib(4) = fib(3) + fib(2) = 2 + 1 = 3

Why: Optimal substructure means fib(4) is best found by combining best answers of fib(3) and fib(2)

Result:

fib(4) = 3
Overlapping subproblems: fib(2) calculated once and reused
Optimal substructure: fib(4) built from fib(3) and fib(2)

Annotated Code

DSA C

#include <stdio.h>

// Recursive Fibonacci with memoization to show overlapping subproblems
int fib(int n, int memo[]) {
    if (n <= 1) return n; // base case
    if (memo[n] != -1) return memo[n]; // reuse stored result
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // combine subproblems
    return memo[n];
}

int main() {
    int n = 4;
    int memo[5];
    for (int i = 0; i <= n; i++) memo[i] = -1; // initialize memo
    int result = fib(n, memo);
    printf("fib(%d) = %d\n", n, result);
    return 0;
}

if (memo[n] != -1) return memo[n];

reuse stored result to avoid recalculating overlapping subproblems

memo[n] = fib(n - 1, memo) + fib(n - 2, memo);

combine best answers of smaller subproblems to build optimal solution

Output

fib(4) = 3

Complexity Analysis

Time: O(n) because each subproblem fib(i) is solved once and reused

Space: O(n) for the memo array storing results of subproblems

vs Alternative: Naive recursion is O(2^n) due to repeated calculations; memoization reduces it to O(n)

Edge Cases

n = 0 or n = 1 (base cases)

Returns n immediately without recursion

DSA C

if (n <= 1) return n;

Repeated calls for same n

Memoization returns stored result, avoiding repeated work

DSA C

if (memo[n] != -1) return memo[n];

When to Use This Pattern

When a problem asks for a solution built from smaller repeated parts, and those parts overlap, use dynamic programming because it saves work by reusing answers.

Common Mistakes

Mistake: Not storing results causes repeated calculations and slow code
Fix: Use a memo array or table to save and reuse subproblem answers

Mistake: Trying to solve subproblems independently without combining results
Fix: Recognize that the final answer is built from best answers of smaller parts

Summary

It breaks problems into smaller overlapping parts and solves each once.

Use it when subproblems repeat and the final answer depends on their best solutions.

The key is to reuse answers to repeated parts and combine them optimally.