Overlapping Subproblems and Optimal Substructure in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does Overlapping Subproblems mean in dynamic programming?

It means the problem can be broken down into smaller subproblems which are solved multiple times. Instead of solving them again, we store their results to save time.

beginner

Define Optimal Substructure in simple words.

A problem has optimal substructure if the best solution to the problem can be made by combining the best solutions to its smaller parts.

intermediate

Why is Overlapping Subproblems important for dynamic programming?

Because it allows us to use memoization or tabulation to avoid repeated work, making the solution faster.

intermediate

Give an example of a problem that shows both overlapping subproblems and optimal substructure.

The Fibonacci sequence problem: calculating Fibonacci numbers involves solving the same smaller Fibonacci problems multiple times (overlapping subproblems), and the best solution for a number depends on the best solutions of the previous two numbers (optimal substructure).

intermediate

How does Optimal Substructure help in designing recursive solutions?

It ensures that solving smaller parts optimally leads to the overall optimal solution, so we can build the answer step-by-step using recursion.

Which of the following best describes overlapping subproblems?

A Subproblems repeat and are solved multiple times

B Subproblems are always larger than the main problem

C Subproblems are unrelated to the main problem

D Subproblems are independent and solved once

Overlapping subproblems means the same smaller problems appear multiple times and can be reused.

What does optimal substructure imply about a problem?

A The problem cannot be divided into smaller parts

B The best solution depends on the best solutions of smaller parts

C The problem has no solution

D The problem is solved only once

Optimal substructure means the overall best solution is made from best solutions of smaller subproblems.

Which problem is a classic example of overlapping subproblems and optimal substructure?

A Sorting an array

B Finding maximum in an array

C Fibonacci sequence calculation

D Linear search

Fibonacci calculation solves the same smaller Fibonacci numbers repeatedly and builds the answer from smaller solutions.

What technique uses overlapping subproblems to improve efficiency?

A Memoization

B Random guessing

C Brute force

D Sorting

Memoization stores results of subproblems to avoid repeated work.

If a problem lacks optimal substructure, what does it mean?

A It is always easy to solve

B We can solve it using dynamic programming

C It has overlapping subproblems

D The best solution cannot be built from smaller best solutions

Without optimal substructure, combining smaller solutions won't guarantee the best overall solution.

Explain in your own words what overlapping subproblems and optimal substructure mean and why they matter in dynamic programming.

Think about solving a problem by breaking it into smaller parts and reusing answers.

Describe a simple example problem that shows both overlapping subproblems and optimal substructure. Explain how these properties appear in that problem.

Consider a problem where you calculate values multiple times and combine smaller answers.

Practice

1. Which of the following best describes the property of Overlapping Subproblems in dynamic programming?

easy

A. The problem can be broken down into smaller subproblems which are solved 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 the solution process.

2. Step 2: Match the definition to 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 A

4. Quick Check:

   Overlapping Subproblems = Smaller repeated subproblems [OK]

Hint: Look for repeated smaller problems in the main problem [OK]

Common Mistakes:

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

2. Which of the following C++ function signatures correctly represents a memoized Fibonacci function using dynamic programming?

easy

A. void fib(int n);

B. int fib();

C. int fib(int n);

D. int fib(int n, int memo[]);

Solution

1. Step 1: Identify memoization parameters

   Memoization requires an extra data structure (like an array) to store results of subproblems.

2. Step 2: Check function signatures

   int fib(int n, int memo[]); includes an array parameter to store memoized results, which is necessary for memoization.

3. Final Answer:

   int fib(int n, int memo[]); -> Option D

4. Quick Check:

   Memoization needs storage parameter [OK]

Hint: Memoized functions need extra storage parameter [OK]

Common Mistakes:

• Ignoring the memo array parameter
• Using void return type for Fibonacci
• Not passing any parameters for recursion

3. What is the output of the following C++ code snippet?

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

int main() {
  int n = 5;
  int memo[6];
  for(int i = 0; i <= n; i++) memo[i] = -1;
  std::cout << fib(n, memo);
  return 0;
}

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Understand Fibonacci calculation

   fib(5) = fib(4) + fib(3). Using memoization, fib(5) = 8.

2. Step 2: Trace the code execution

   Memo array initialized with -1, so recursive calls compute and store values. fib(5) returns 8.

3. Final Answer:

   8 -> Option B

4. Quick Check:

   fib(5) = 8 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Forgetting zero-based indexing
• Assuming memo array is not initialized

4. Identify the error in the following code snippet implementing memoized Fibonacci:

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

medium

A. The function should return void instead of int.

B. Base cases should return -1 instead of 0 or 1.

C. Memo array should be initialized with -1, not 0.

D. The memo array size is not checked inside the function.

Solution

1. Step 1: Check memoization condition

   The code checks if memo[n] != 0 to decide if value is computed, but 0 is a valid Fibonacci value.

2. Step 2: Correct initialization for memo array

   Memo array should be initialized with a value like -1 to indicate uncomputed states, avoiding confusion with valid 0.

3. Final Answer:

   Memo array should be initialized with -1, not 0. -> Option C

4. Quick Check:

   Use -1 for uninitialized memo values [OK]

Hint: Initialize memo with -1 to distinguish computed from uncomputed [OK]

Common Mistakes:

• Using 0 as default memo value causing wrong cache hits
• Changing base case return values incorrectly
• Ignoring memo array size checks

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 both overlapping subproblems and optimal substructure.

B. The problem has optimal substructure but no overlapping subproblems.

C. The problem has overlapping subproblems but no optimal substructure.

D. The problem has neither overlapping subproblems nor optimal substructure.

Solution

1. Step 1: Understand minimum cost path problem

   The problem breaks into smaller subproblems (paths to cells) that overlap and solutions combine optimally.

2. Step 2: Identify properties

   It has overlapping subproblems (same cells computed multiple times) and optimal substructure (optimal path uses optimal subpaths).

3. Final Answer:

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

4. Quick Check:

   Minimum cost path = Overlapping + Optimal substructure [OK]

Hint: Check if subproblems repeat and combine optimally [OK]

Common Mistakes:

• Thinking only one property applies
• Confusing optimal substructure with greedy choice
• Ignoring repeated subproblems in grid paths