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

Recall & Review

beginner

What does the term 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 repeatedly, we store their results to avoid repeated work.

beginner

Define Optimal Substructure in simple terms.

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 memoization important for overlapping subproblems?

Memoization saves the results of subproblems so they don’t have to be recalculated, making the program faster and more efficient.

beginner

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 repeatedly (overlapping subproblems), and the solution for a number depends on the solutions of smaller numbers (optimal substructure).

intermediate

How does dynamic programming use overlapping subproblems and optimal substructure?

Dynamic programming solves problems by breaking them into smaller subproblems (optimal substructure) and storing their results to avoid repeated work (overlapping subproblems).

What is the main benefit of overlapping subproblems in dynamic programming?

A We can reuse solutions to subproblems to save time

B We can ignore smaller problems

C We solve each subproblem only once

D We avoid breaking problems into smaller parts

Overlapping subproblems allow us to reuse solutions to subproblems, which saves time by avoiding repeated calculations.

Which property means the best solution to a problem depends on best solutions to smaller problems?

A Overlapping Subproblems

B Divide and Conquer

C Greedy Choice Property

D Optimal Substructure

Optimal Substructure means the best solution can be built from best solutions of smaller parts.

Which technique stores results of subproblems to avoid recomputation?

A Memoization

B Sorting

C Backtracking

D Brute Force

Memoization saves results of subproblems to avoid recalculating them.

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

A Sorting an Array

B Binary Search

C Fibonacci Sequence

D Finding Maximum

Fibonacci sequence calculation repeats subproblems and builds solutions from smaller Fibonacci numbers.

Dynamic programming is best used when a problem has:

A No subproblems

B Overlapping subproblems and optimal substructure

C Only one solution path

D Random inputs

Dynamic programming works well when problems have overlapping subproblems and optimal substructure.

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

Think about breaking problems into smaller parts and reusing solutions.

Describe a simple example problem that shows overlapping subproblems and optimal substructure and explain how dynamic programming solves it.

Use a problem where smaller answers help build bigger answers.

Practice

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

easy

A. The problem has a unique solution that can be found without recursion.

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

C. The problem requires sorting before solving.

D. The problem can only be solved using greedy algorithms.

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 B

4. Quick Check:

   Overlapping Subproblems = The problem can be broken down into smaller subproblems which are solved multiple times. [OK]

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

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking greedy algorithms always apply
• Ignoring recursion or repeated calculations

2. Which of the following C# method signatures correctly represents a memoized Fibonacci function using recursion?

easy

A. string Fib(int n, Dictionary memo)

B. void Fib(int n)

C. int Fib(int n, int[] memo)

D. int Fib(int n, Dictionary memo)

Solution

1. Step 1: Identify correct return type and parameters

   The Fibonacci function returns an integer and uses a dictionary to store computed values for memoization.

2. Step 2: Check options for matching signature

   int Fib(int n, Dictionary memo) returns int and takes an int and a Dictionary for memo, which is correct for memoized recursion.

3. Final Answer:

   int Fib(int n, Dictionary memo) -> Option D

4. Quick Check:

   Memoized Fib signature = int Fib(int n, Dictionary memo) [OK]

Hint: Memoized functions usually take a cache parameter like Dictionary [OK]

Common Mistakes:

• Using void return type instead of int
• Using wrong data structure for memo
• Returning string instead of int

3. What is the output of the following C# code?

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

static void Main() {
  int n = 5;
  int[] memo = new int[n + 1];
  Console.WriteLine(Fib(n, memo));
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Understand Fibonacci calculation for n=5

   Fibonacci sequence: 0,1,1,2,3,5,... So Fib(5) = 5.

2. Step 2: Trace memoized calls

   Memo array caches results to avoid repeated calls, final result printed is Fib(5) = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence values for small n [OK]

Common Mistakes:

• Confusing Fib(5) with Fib(6)
• Ignoring memoization effect
• Assuming zero-based indexing for output

4. Identify the error in the following C# code implementing a memoized Fibonacci function:

static 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];
}

static void Main() {
  int n = 4;
  int[] memo = new int[n + 1];
  Console.WriteLine(Fib(n, memo));
}

medium

A. The memo array is not initialized with -1, so memo[n] != -1 check fails.

B. The base case should return 0 instead of n.

C. The function should return void instead of int.

D. The memo array size is too large.

Solution

1. Step 1: Check memo array initialization

   The memo array is created but not initialized to -1, so all values default to 0.

2. Step 2: Analyze memo[n] != -1 condition

   Since memo[n] starts at 0, the condition memo[n] != -1 is always true for n>0, causing incorrect memo hits.

3. Final Answer:

   The memo array is not initialized with -1, so memo[n] != -1 check fails. -> Option A

4. Quick Check:

   Uninitialized memo array causes wrong memo check [OK]

Hint: Initialize memo with sentinel values matching your check [OK]

Common Mistakes:

• Not initializing memo array properly
• Incorrect base case return values
• Wrong return type for recursive function

5. You want to find the minimum cost path in a grid from top-left to bottom-right, moving only right or down. The cost grid is:

int[,] cost = {
  {1, 3, 5, 8},
  {4, 2, 1, 7},
  {4, 3, 2, 3}
};

Which approach best uses Overlapping Subproblems and Optimal Substructure to solve this efficiently?

hard

A. Calculate all paths and pick the minimum cost path at the end.

B. Use a greedy approach picking the minimum cost neighbor at each step.

C. Use recursion with memoization to store minimum cost for each cell.

D. Use a stack to store all possible paths and backtrack.

Solution

1. Step 1: Understand problem structure

   The minimum cost path problem has overlapping subproblems because many paths share subpaths, and optimal substructure because the best path to a cell depends on best paths to neighbors.

2. Step 2: Choose efficient approach

   Recursion with memoization stores results of subproblems to avoid recomputation, efficiently solving the problem.

3. Final Answer:

   Use recursion with memoization to store minimum cost for each cell. -> Option C

4. Quick Check:

   Memoized recursion fits overlapping subproblems and optimal substructure [OK]

Hint: Memoize subproblem results to avoid repeated calculations [OK]

Common Mistakes:

• Using greedy approach which may fail for this problem
• Trying all paths causing exponential time
• Using stack/backtracking without memoization