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.

Practice

1. Which of the following best describes the concept of overlapping subproblems in dynamic programming?

easy

A. The problem requires sorting elements before solving.

B. The problem has a unique solution without repeating any subproblems.

C. The problem can be broken down into smaller subproblems which are solved multiple times.

D. The problem can be solved only using recursion without optimization.

Solution

1. Step 1: Understand overlapping subproblems

   Overlapping subproblems means the same smaller problems appear multiple times during the solution process.

2. Step 2: Match with options

   The problem can be broken down into smaller subproblems which are solved multiple times. correctly states that subproblems are solved multiple times, which is the key idea behind overlapping subproblems.

3. Final Answer:

   The problem can be broken down into smaller subproblems which are solved multiple times. -> Option C

4. Quick Check:

   Overlapping subproblems = repeated smaller problems [OK]

Hint: Look for repeated smaller problems solved multiple times [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking sorting is required for overlapping subproblems
• Assuming recursion alone solves overlapping subproblems

2. Which of the following is the correct syntax to declare a memoization array for storing results of subproblems in C?

easy

A. int memo[] = 0;

B. int memo = new int[1000];

C. int memo(1000);

D. int memo[1000] = {0};

Solution

1. Step 1: Understand C array declaration

   In C, arrays are declared with fixed size and can be initialized with {0} to set all elements to zero.

2. Step 2: Check options for valid C syntax

   int memo[1000] = {0}; uses correct C syntax: int memo[1000] = {0}; initializes an array of 1000 integers to zero.

3. Final Answer:

   int memo[1000] = {0}; -> Option D

4. Quick Check:

   C array declaration with initialization = int memo[1000] = {0}; [OK]

Hint: Use fixed size array with braces to initialize in C [OK]

Common Mistakes:

• Using C++ style vector or new keyword in C
• Declaring arrays without size
• Incorrect initialization syntax

3. Consider the following C code for Fibonacci with memoization:

int memo[100] = {0};

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

int main() {
    printf("%d", fib(5));
    return 0;
}

What is the output when this code runs?

medium

A. 0

B. 5

C. 3

D. 8

Solution

1. Step 1: Trace fib(5) calls with memoization

   fib(5) calls fib(4) + fib(3). fib(4) calls fib(3) + fib(2), and so on. Base cases fib(0)=0, fib(1)=1.

2. Step 2: Calculate fib(5)

   fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=fib(4)+fib(3)=3+2=5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Recall Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing index with Fibonacci value
• Ignoring memoization effect
• Miscomputing base cases

4. The following code attempts to compute the nth Fibonacci number using memoization but has a bug:

int memo[100] = {0};

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

int main() {
    printf("%d", fib(0));
    return 0;
}

What is the bug in this code?

medium

A. fib(0) returns 0 but memo[0] is never set, causing repeated calls.

B. The memo array is not initialized to zero.

C. The base case for fib(1) is missing.

D. The memoization check uses wrong index.

Solution

1. Step 1: Analyze base cases and memo usage

   fib(0) returns 0 but does not store it in memo[0]. So memo[0] remains 0, which is the default value.

2. Step 2: Understand effect on memoization

   Because the base case results are not stored in memo[n], fib(0) (and fib(1)) will be called repeatedly in the recursion tree for larger n, instead of returning a cached value.

3. Final Answer:

   fib(0) returns 0 but memo[0] is never set, causing repeated calls. -> Option A

4. Quick Check:

   Base case not stored in memo causes repeated calls [OK]

Hint: Store base case results in memo to avoid repeated calls [OK]

Common Mistakes:

• Assuming memo array auto-initializes for base cases
• Missing base case for fib(1)
• Incorrect memo check condition

5. You want to find the minimum cost to reach the top of stairs where each step has a cost. You can climb 1 or 2 steps at a time. The cost array is cost[] = {10, 15, 20}. Using dynamic programming with overlapping subproblems and optimal substructure, what is the minimum cost to reach the top (beyond last step)?

hard

A. 15

B. 20

C. 25

D. 10

Solution

1. Step 1: Define subproblems and recurrence

   Minimum cost to reach step i: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). dp[0]=10, dp[1]=15.

2. Step 2: Calculate minimum cost step by step

   dp[2] = 20 + min(10,15) = 30. To reach top (beyond last step), min(dp[1], dp[2]) = min(15,30) = 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Minimum cost to top = 15 [OK]

Hint: Use min cost of last two steps for final answer [OK]

Common Mistakes:

• Adding all costs instead of choosing min path
• Ignoring that you can start from step 0 or 1
• Confusing cost to step vs cost beyond last step