Overlapping Subproblems and Optimal Substructure in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following C# code that calculates Fibonacci numbers using memoization?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static Dictionary<int, int> memo = new Dictionary<int, int>();

    static int Fib(int n) {
        if (n <= 1) return n;
        if (memo.ContainsKey(n)) return memo[n];
        int result = Fib(n - 1) + Fib(n - 2);
        memo[n] = result;
        return result;
    }

    static void Main() {
        Console.WriteLine(Fib(6));
    }
}

A 21

B 5

C 13

D 8

💡 Hint

Recall that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13...

The Fibonacci sequence with Fib(0)=0 and Fib(1)=1 produces Fib(6) = 8. The memo dictionary stores intermediate results to avoid repeated calculations.

🧠 Conceptual

intermediate

Identifying Optimal Substructure

Which of the following problems exhibits optimal substructure, meaning the optimal solution can be constructed from optimal solutions of its subproblems?

A Finding the shortest path in a graph using Dijkstra's algorithm

B Sorting an array using bubble sort

C Checking if a number is prime

D Printing all permutations of a string

💡 Hint

Optimal substructure means the problem can be broken down into smaller problems whose solutions combine to solve the bigger problem optimally.

Dijkstra's algorithm relies on optimal substructure: shortest paths to intermediate nodes are used to find shortest paths to further nodes.

🔧 Debug

advanced

Debugging Memoization in Recursive Solution

The following C# code attempts to compute the minimum cost path in a grid using memoization but produces incorrect results. What is the main bug?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int[,] grid = { {1, 3, 5}, {2, 1, 2}, {4, 3, 1} };
    static Dictionary<(int,int), int> memo = new Dictionary<(int,int), int>();

    static int MinCost(int r, int c) {
        if (r == 0 && c == 0) return grid[0,0];
        if (r < 0 || c < 0) return int.MaxValue;
        if (memo.ContainsKey((r,c))) return memo[(r,c)];

        int up = MinCost(r - 1, c);
        int left = MinCost(r, c - 1);
        int result = grid[r,c] + Math.Min(up, left);
        // Missing memoization store here
        return result;
    }

    static void Main() {
        Console.WriteLine(MinCost(2, 2));
    }
}

A The memo dictionary is never updated with computed results.

B The base case for (0,0) is incorrect and should return 0.

C The grid indices are accessed out of bounds causing runtime error.

D The recursive calls do not handle negative indices properly.

💡 Hint

Check if the memo dictionary is used to store results after computation.

The code never stores computed results in memo, so memoization does not work and causes repeated calculations.

❓ Predict Output

advanced

Output of Longest Common Subsequence Length

What is the output of the following C# code that computes the length of the longest common subsequence (LCS) between two strings using recursion with memoization?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static Dictionary<(int,int), int> memo = new Dictionary<(int,int), int>();

    static int LCS(string s1, string s2, int i, int j) {
        if (i == s1.Length || j == s2.Length) return 0;
        if (memo.ContainsKey((i,j))) return memo[(i,j)];

        if (s1[i] == s2[j]) {
            memo[(i,j)] = 1 + LCS(s1, s2, i + 1, j + 1);
        } else {
            memo[(i,j)] = Math.Max(LCS(s1, s2, i + 1, j), LCS(s1, s2, i, j + 1));
        }
        return memo[(i,j)];
    }

    static void Main() {
        Console.WriteLine(LCS("AGGTAB", "GXTXAYB", 0, 0));
    }
}

A 6

B 5

C 4

D 7

💡 Hint

The longest common subsequence between "AGGTAB" and "GXTXAYB" is "GTAB" (length 4).

The LCS length is 4 for these strings, computed by recursive memoized calls.

🧠 Conceptual

expert

Recognizing Overlapping Subproblems in Algorithms

Which of the following algorithms does NOT exhibit overlapping subproblems, meaning it does not solve the same subproblems multiple times?

A Computing Fibonacci numbers using naive recursion

B Merge sort algorithm

C Calculating binomial coefficients using Pascal's triangle with memoization

D Solving the knapsack problem using dynamic programming

💡 Hint

Overlapping subproblems means the algorithm solves the same smaller problem multiple times.

Merge sort divides the array into halves and sorts each half independently without recomputing the same subproblems multiple times.

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