Overlapping Subproblems and Optimal Substructure in DSA Python

Mental Model

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

Analogy: Imagine building a big Lego castle by reusing the same small Lego pieces many times instead of making new ones each time.

Problem
  ↓
Subproblem A -> Subproblem B -> Subproblem C
  ↓           ↓
Subproblem A (repeated)  Subproblem B (repeated)

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using recursion

Goal: Show how the same smaller problems are solved multiple times and how remembering them helps

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

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

Why: fib(5) depends on fib(4) and fib(3)

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

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

Why: fib(4) depends on fib(3) and fib(2)

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

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

Why: fib(3) depends on fib(2) and fib(1), fib(3) repeats

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

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

Why: fib(2) depends on fib(1) and fib(0), fib(2) repeats

Step 5: Recognize fib(3) and fib(2) are calculated multiple times

fib(3) and fib(2) repeated calculations

Why: This is overlapping subproblems

Step 6: Use stored results of fib(3) and fib(2) to avoid repeated work

fib(5) calculated efficiently by reusing fib(3) and fib(2)

Why: Optimal substructure means best solution uses best smaller solutions

Result:

fib(5) = 5
Overlapping subproblems: fib(3), fib(2) repeated
Optimal substructure: fib(5) = fib(4) + fib(3)

Annotated Code

DSA Python

class Fibonacci:
    def __init__(self):
        self.memo = {}

    def fib(self, n: int) -> int:
        if n in self.memo:
            return self.memo[n]  # reuse stored result to avoid repeated work
        if n <= 1:
            self.memo[n] = n  # base case: fib(0)=0, fib(1)=1
            return n
        # calculate fib(n-1) and fib(n-2) recursively
        result = self.fib(n - 1) + self.fib(n - 2)
        self.memo[n] = result  # store result for reuse
        return result

# Driver code
fib_calc = Fibonacci()
print(fib_calc.fib(5))

if n in self.memo:

check if result for n is already computed to reuse it

if n <= 1:

handle base cases fib(0)=0 and fib(1)=1

result = self.fib(n - 1) + self.fib(n - 2)

compute fib(n) using results of smaller subproblems

self.memo[n] = result

store computed result to avoid repeated calculations

Output

5

Complexity Analysis

Time: O(n) because each fib number from 0 to n is computed once and reused

Space: O(n) for the memo dictionary storing results for each subproblem

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

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Python

if n <= 1:

n = 1

Returns 1 immediately as base case

DSA Python

if n <= 1:

Repeated calls with same n

Uses memo to return result instantly without recomputation

DSA Python

if n in self.memo:

When to Use This Pattern

When a problem asks for a solution that can be broken into smaller repeated parts, look for overlapping subproblems and optimal substructure to use memoization or dynamic programming.

Common Mistakes

Mistake: Not storing computed results causes repeated work and slow performance
Fix: Use a memo dictionary to save and reuse results of subproblems

Mistake: Missing base cases leads to infinite recursion
Fix: Always define base cases like fib(0) and fib(1) to stop recursion

Summary

It breaks problems into smaller repeated parts and uses best answers to those parts to build the final solution.

Use it when a problem can be divided into overlapping smaller problems with optimal substructure.

The key insight is that solving and remembering smaller parts once saves time and builds the best overall answer.

Practice

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

easy

A. The problem can be broken down into smaller subproblems that are reused multiple times.

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

C. The problem requires sorting before solving.

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

Solution

1. Step 1: Understand overlapping subproblems

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

2. Step 2: Match definition to options

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

3. Final Answer:

   The problem can be broken down into smaller subproblems that are reused multiple times. -> Option A

4. Quick Check:

   Overlapping subproblems = reuse of subproblems [OK]

Hint: Look for repeated smaller problems in the main problem [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 Python function definitions correctly uses memoization to solve overlapping subproblems?

easy

A. def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2)

B. def fib(n): return n * fib(n-1)

C. def fib(n): for i in range(n): print(i)

D. def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: memo[n] = n else: memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n]

Solution

1. Step 1: Identify memoization usage

   Memoization stores results of subproblems to avoid repeated work, usually with a dictionary.

2. Step 2: Check each option

   def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: memo[n] = n else: memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] uses a dictionary 'memo' to save and reuse results, correctly implementing memoization.

3. Final Answer:

   def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: memo[n] = n else: memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n] -> Option D

4. Quick Check:

   Memoization = caching results [OK]

Hint: Look for a cache (dictionary) storing computed results [OK]

Common Mistakes:

• Missing memo dictionary parameter
• Not returning cached results
• Using loops without caching results

3. What is the output of the following code?

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))

medium

A. 13

B. 8

C. 5

D. 3

Solution

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

   fib(5) calls fib(4) and fib(3), which further call smaller fib values, caching results to avoid repeats.

2. Step 2: Calculate fib(5)

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Miscounting base cases

4. The following code attempts to use memoization for Fibonacci numbers but has a bug. What is the error?

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

print(fib(4))

medium

A. Missing memo argument in recursive calls causes infinite recursion.

B. Base case is incorrect for n <= 1.

C. Memo dictionary is not initialized.

D. Return statement is missing.

Solution

1. Step 1: Check recursive calls

   Recursive calls fib(n-1) and fib(n-2) do not pass 'memo', so memo is empty each time.

2. Step 2: Understand effect of missing memo argument

   Without passing memo, caching fails and recursion repeats infinitely, causing a stack overflow.

3. Final Answer:

   Missing memo argument in recursive calls causes infinite recursion. -> Option A

4. Quick Check:

   Pass memo in recursive calls to fix [OK]

Hint: Always pass memo/cache in recursive calls [OK]

Common Mistakes:

• Forgetting to pass memo in recursive calls
• Assuming base case alone stops recursion
• Not initializing memo outside function

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. Which approach best uses optimal substructure and overlapping subproblems to solve this?

hard

A. Use recursion without caching to try all paths.

B. Use dynamic programming to store minimum cost for each step and build up solution.

C. Sort the costs and pick the smallest steps first.

D. Use a greedy approach to always pick the next step with minimum cost.

Solution

1. Step 1: Understand problem structure

   Minimum cost to reach step i depends on minimum cost to reach steps i-1 and i-2 plus cost at i.

2. Step 2: Apply dynamic programming

   Store minimum costs for each step to avoid recomputing (overlapping subproblems) and use previous results (optimal substructure).

3. Final Answer:

   Use dynamic programming to store minimum cost for each step and build up solution. -> Option B

4. Quick Check:

   DP uses optimal substructure + overlapping subproblems [OK]

Hint: Build solution step-by-step storing results [OK]

Common Mistakes:

• Using recursion without memoization causing slow solution
• Trying greedy approach which may fail
• Sorting costs which is irrelevant