Overlapping Subproblems and Optimal Substructure in DSA Java - Execution Trace

Concept Flow - Overlapping Subproblems and Optimal Substructure

Problem

→Break into Subproblems

↓

Check if Subproblem

↓

Use stored solution

| No↓

Compute Subproblem

↓

Combine Subproblem Solutions

↓

Final Solution

The problem is broken into smaller subproblems. If a subproblem repeats, reuse its solution (overlapping subproblems). Combine these solutions to solve the main problem (optimal substructure).

Execution Sample

DSA Java

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

Calculates Fibonacci number using recursion, showing overlapping subproblems and optimal substructure.

Execution Table

Step	Operation	Subproblem	Is Cached?	Action	Result	Visual State
1	Call fib(4)	fib(4)	No	Compute fib(3) + fib(2)	Pending	fib(4) waiting for fib(3) and fib(2)
2	Call fib(3)	fib(3)	No	Compute fib(2) + fib(1)	Pending	fib(3) waiting for fib(2) and fib(1)
3	Call fib(2)	fib(2)	No	Compute fib(1) + fib(0)	Pending	fib(2) waiting for fib(1) and fib(0)
4	Call fib(1)	fib(1)	No	Return 1	1	fib(1) = 1
5	Call fib(0)	fib(0)	No	Return 0	0	fib(0) = 0
6	Compute fib(2)	fib(2)	No	fib(1)+fib(0) = 1+0	1	fib(2) = 1 stored
7	Call fib(1)	fib(1)	Yes	Use cached 1	1	fib(1) reused
8	Compute fib(3)	fib(3)	No	fib(2)+fib(1) = 1+1	2	fib(3) = 2 stored
9	Call fib(2)	fib(2)	Yes	Use cached 1	1	fib(2) reused
10	Compute fib(4)	fib(4)	No	fib(3)+fib(2) = 2+1	3	fib(4) = 3 stored
11	Return fib(4)	fib(4)	Yes	Return cached 3	3	Final result fib(4) = 3

💡 fib(4) computed using cached subproblems fib(3) and fib(2), recursion ends.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 8	After Step 10	Final
fib(4)	Not computed	Not computed	Not computed	Not computed	3	3
fib(3)	Not computed	Not computed	Not computed	2	2	2
fib(2)	Not computed	Not computed	1	1	1	1
fib(1)	Not computed	1	1	1	1	1
fib(0)	Not computed	0	0	0	0	0

Key Moments - 3 Insights

Why do we reuse the result of fib(2) instead of computing it again?

Because fib(2) is an overlapping subproblem that appears multiple times. The execution_table rows 6 and 9 show fib(2) is computed once and reused later, saving time.

How does optimal substructure help in solving fib(4)?

fib(4) is solved by combining solutions of smaller subproblems fib(3) and fib(2), as shown in execution_table rows 1 and 10. This shows the problem can be built from optimal solutions of its parts.

What happens if we don't store subproblem results?

Without storing, the same subproblems like fib(2) and fib(1) would be recomputed multiple times, causing redundant work and slower execution, as seen in the repeated calls before caching in the table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result of fib(3) at step 8?

A 1

B 2

C 3

D Pending

💡 Hint

Check the 'Result' column at step 8 in the execution_table.

At which step does fib(2) get reused from cache?

A Step 9

B Step 6

C Step 3

D Step 10

💡 Hint

Look for 'Is Cached?' marked Yes for fib(2) in the execution_table.

If we remove caching, how would the number of calls to fib(2) change?

A Decrease

B Stay the same

C Increase

D Become zero

💡 Hint

Refer to key_moments explaining repeated computation without caching.

Concept Snapshot

Overlapping Subproblems and Optimal Substructure:
- Break problem into smaller subproblems.
- Reuse solutions of repeated subproblems (overlapping).
- Combine optimal subproblem solutions for final answer.
- Enables efficient algorithms like dynamic programming.
- Example: Fibonacci uses cached fib(n-1) and fib(n-2).

Full Transcript

This concept shows how some problems can be split into smaller parts that repeat. Instead of solving the same part many times, we save the answer and reuse it. This is called overlapping subproblems. Also, the best answer to the big problem comes from best answers to smaller parts, called optimal substructure. For example, Fibonacci numbers are calculated by adding two smaller Fibonacci numbers. We use caching to avoid repeated work, making the solution faster and efficient.

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