Overlapping Subproblems and Optimal Substructure in DSA Java

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 the same small Lego pieces multiple times instead of making new ones each time.

Problem
  ↓
Subproblem A ←─┐
  ↓           │
Subproblem B ─┘
  ↓
Solution

Dry Run Walkthrough

Input: Calculate Fibonacci number for 5 using recursion

Goal: Show how the same smaller problems are solved multiple times and how using their answers saves work

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

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

Why: To find fib(5), we need fib(4) and fib(3)

Step 2: Calculate fib(4) by calling 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), but fib(3) is repeated

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

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

Why: fib(3) is calculated multiple times, showing overlapping subproblems

Step 4: Reuse fib(3) result when calculating fib(5) after fib(4)

fib(5) uses stored fib(3) instead of recalculating

Why: Storing answers avoids repeating work, showing optimal substructure

Result:

fib(5) = 5
Overlapping subproblems: fib(3) calculated multiple times
Optimal substructure: fib(5) built from best fib(4) and fib(3)

Annotated Code

DSA Java

public class Fibonacci {
    // Calculate Fibonacci number with memoization to avoid repeated work
    public static 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];
    }

    public static void main(String[] args) {
        int n = 5;
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) memo[i] = -1; // initialize memo
        int result = fib(n, memo);
        System.out.println("fib(" + n + ") = " + result);
    }
}

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 solutions of smaller subproblems to build optimal solution

Output

fib(5) = 5

Complexity Analysis

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

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 (smallest inputs)

Returns n immediately as base case

DSA Java

if (n <= 1) return n;

Large n with memoization

Efficiently computes without repeated work

DSA Java

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

When to Use This Pattern

When a problem asks for a solution built from smaller repeated parts, look for overlapping subproblems and optimal substructure to use dynamic programming.

Common Mistakes

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

Summary

It breaks problems into smaller parts that repeat and uses their best answers to build the final solution.

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

The key is to store answers to repeated parts so you don't solve the same thing twice.

Practice

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

easy

A. The problem has no repeated subproblems and each subproblem is unique.

B. The problem can be broken into smaller subproblems that are solved multiple times.

C. The solution requires sorting the input data first.

D. The problem can be solved using a greedy approach without recursion.

Solution

1. Step 1: Understand overlapping subproblems

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

2. Step 2: Match with options

   The problem can be broken into smaller subproblems that are solved multiple times. correctly states that subproblems repeat and are solved multiple times.

3. Final Answer:

   The problem can be broken into smaller subproblems that are solved multiple times. -> Option B

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
• Mixing greedy approach with dynamic programming

2. Which of the following Java method signatures correctly represents a memoized Fibonacci function?

easy

A. public int fib(int n, int[] memo)

B. public void fib(int n)

C. public int fib(String n, int[] memo)

D. public int fib(int n, String[] memo)

Solution

1. Step 1: Identify correct parameter types

   Memoization requires storing results, so an int array for memo is needed. The input n should be int.

2. Step 2: Check method signatures

   public int fib(int n, int[] memo) uses int n and int[] memo, which is correct for memoized Fibonacci.

3. Final Answer:

   public int fib(int n, int[] memo) -> Option A

4. Quick Check:

   Memo array type matches input type [OK]

Hint: Memo array must match return type and input must be int [OK]

Common Mistakes:

• Using void return type for Fibonacci function
• Using String type for numeric input or memo array
• Not passing memo array as parameter

3. What is the output of the following Java code snippet implementing a simple memoized Fibonacci?

public class FibMemo {
    static int[] memo = new int[6];
    public static 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];
    }
    public static void main(String[] args) {
        System.out.println(fib(5));
    }
}

medium

A. 8

B. 0

C. 5

D. StackOverflowError

Solution

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

   fib(5) calls fib(4) and fib(3), and so on. Memo stores 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: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Expecting sum of all calls instead of fib(5)

4. Identify the error in this Java code snippet for computing Fibonacci with memoization:

public class Fib {
    static int[] memo = new int[5];
    public static 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];
    }
    public static void main(String[] args) {
        System.out.println(fib(5));
    }
}

medium

A. No error, prints correct Fibonacci number

B. StackOverflowError due to infinite recursion

C. Compilation error due to missing return

D. ArrayIndexOutOfBoundsException due to memo size

Solution

1. Step 1: Check memo array size and access

   Memo array size is 5, so valid indices are 0 to 4. fib(5) tries to access memo[5], causing error.

2. Step 2: Identify exception type

   Accessing memo[5] causes ArrayIndexOutOfBoundsException at runtime.

3. Final Answer:

   ArrayIndexOutOfBoundsException due to memo size -> Option D

4. Quick Check:

   Array size < access index = error [OK]

Hint: Check array size matches max index accessed [OK]

Common Mistakes:

• Assuming memo size is enough without checking
• Thinking recursion causes stack overflow here
• Ignoring runtime exceptions

5. Given the problem of finding the minimum cost path in a grid from top-left to bottom-right, which property justifies using dynamic programming to solve it efficiently?

hard

A. The problem has overlapping subproblems and optimal substructure.

B. The problem can be solved by sorting all paths.

C. The problem requires only greedy choices without recursion.

D. The problem has no repeated subproblems and no optimal substructure.

Solution

1. Step 1: Understand minimum cost path problem

   The problem breaks into smaller subproblems (cost to reach each cell) that overlap.

2. Step 2: Check properties for dynamic programming

   Optimal substructure means optimal solution uses optimal solutions of subproblems. Overlapping subproblems means subproblems repeat.

3. Step 3: Match with options

   The problem has overlapping subproblems and optimal substructure. correctly states both properties, justifying dynamic programming.

4. Final Answer:

   The problem has overlapping subproblems and optimal substructure. -> Option A

5. Quick Check:

   Overlapping subproblems + optimal substructure = DP [OK]

Hint: Look for repeated subproblems and optimal smaller solutions [OK]

Common Mistakes:

• Thinking sorting solves the problem
• Assuming greedy approach always works
• Ignoring overlapping subproblems