Memoization Top Down DP in DSA C# - Build from Scratch

Memoization Top Down DP

📖 Scenario: You are helping a farmer count the number of ways to climb a staircase with n steps. The farmer can climb either 1 or 2 steps at a time. To avoid repeated work, you will use a technique called memoization to remember results for smaller steps.

🎯 Goal: Build a program that uses memoization (top-down dynamic programming) to efficiently calculate the number of ways to climb n steps.

📋 What You'll Learn

Create an integer variable n with the value 5

Create a dictionary called memo to store intermediate results

Write a recursive function CountWays that uses memo to avoid repeated calculations

Print the number of ways to climb n steps

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world problems like calculating Fibonacci numbers, optimizing routes, and solving puzzles efficiently.

💼 Career

Understanding memoization and dynamic programming is important for software engineers to write efficient algorithms and solve complex problems quickly.

1

Create the number of steps variable

Create an integer variable called n and set it to 5.

DSA C#

# Create an integer variable called n and set it to 5
# Your code here

Hint

Use int n = 5; to create the variable.

2

Create the memo dictionary

Create a dictionary called memo of type Dictionary<int, int> to store intermediate results for each step count.

DSA C#

int n = 5;
// Create a dictionary called memo to store intermediate results
// Your code here

Hint

Use var memo = new Dictionary<int, int>(); to create the dictionary.

3

Write the recursive CountWays function with memoization

Write a recursive function called CountWays that takes an integer steps and returns the number of ways to climb those steps. Use the memo dictionary to return stored results if available. If steps is 0 or 1, return 1. Otherwise, return the sum of CountWays(steps - 1) and CountWays(steps - 2), storing the result in memo before returning.

DSA C#

int n = 5;
var memo = new Dictionary();

// Write the CountWays function below
// Your code here

Hint

Use recursion with base cases for 0 and 1 steps. Check memo before computing. Store results in memo.

4

Print the number of ways to climb n steps

Print the result of calling CountWays with n as the argument.

DSA C#

int n = 5;
var memo = new Dictionary();

int CountWays(int steps)
{
    if (steps == 0 || steps == 1)
        return 1;
    if (memo.ContainsKey(steps))
        return memo[steps];
    int result = CountWays(steps - 1) + CountWays(steps - 2);
    memo[steps] = result;
    return result;
}

// Print the number of ways to climb n steps
// Your code here

Hint

Use Console.WriteLine(CountWays(n)); to print the result.

Practice

1. What is the main purpose of memoization in a top-down dynamic programming approach?

easy

A. To store results of subproblems to avoid repeated calculations

B. To sort the input data before processing

C. To convert recursive code into iterative code

D. To reduce the memory usage by deleting intermediate results

Solution

1. Step 1: Understand memoization concept

   Memoization saves the results of subproblems so they are not recalculated multiple times.

2. Step 2: Compare options

   Only To store results of subproblems to avoid repeated calculations correctly describes this purpose. Sorting, converting recursion to iteration, or deleting results are unrelated.

3. Final Answer:

   To store results of subproblems to avoid repeated calculations -> Option A

4. Quick Check:

   Memoization = store subproblem results [OK]

Hint: Memoization means saving answers to reuse later [OK]

Common Mistakes:

• Confusing memoization with sorting or iteration
• Thinking memoization reduces memory by deleting data
• Assuming memoization changes recursion to iteration

2. Which of the following is the correct way to declare a memoization dictionary for integer keys and values in C#?

easy

A. int[] memo = new int();

B. List<int> memo = new List<int>();

C. Dictionary memo = new Dictionary();

D. HashSet<int> memo = new HashSet<int>();

Solution

1. Step 1: Identify suitable data structure for memoization

   Memoization requires storing key-value pairs, so Dictionary is appropriate.

2. Step 2: Check other options

   List<int> and int[] store only values without keys. HashSet<int> stores unique values but no key-value pairs.

3. Final Answer:

   Dictionary memo = new Dictionary(); -> Option C

4. Quick Check:

   Memo dictionary = Dictionary [OK]

Hint: Memo needs key-value pairs, so use Dictionary [OK]

Common Mistakes:

• Using List or array which lack keys
• Using HashSet which stores only unique values
• Incorrect syntax for dictionary declaration

3. What will be the output of the following C# code snippet using memoization for Fibonacci numbers?

using System;
using System.Collections.Generic;

class Program {
  static Dictionary memo = new Dictionary();

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

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

medium

A. 8

B. 5

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   Fib(5) = Fib(4) + Fib(3). 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 B

4. Quick Check:

   Fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing index starting point (0 or 1)
• Forgetting memoization does not change result
• Calculating Fib(5) as 8 or 13 incorrectly

4. Identify the error in the following memoized Fibonacci function and select the correct fix:

static Dictionary memo = new Dictionary();

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);
  return result;
}

medium

A. Change if (n <= 1) return n; to if (n < 0) return 0;

B. Change Dictionary to List<int> for memo

C. Remove memo.ContainsKey check to simplify code

D. Add memo[n] = result; before returning result

Solution

1. Step 1: Check memoization usage

   The function calculates result but never stores it in memo, so memoization fails.

2. Step 2: Fix by storing result in memo

   Adding memo[n] = result; before return saves the computed value for reuse.

3. Final Answer:

   Add memo[n] = result; before returning result -> Option D

4. Quick Check:

   Store result in memo before return [OK]

Hint: Always save computed result in memo before returning [OK]

Common Mistakes:

• Forgetting to store result in memo dictionary
• Changing base case incorrectly
• Removing memo check causing repeated work

5. You want to find the number of ways to climb a staircase of n steps, taking 1 or 2 steps at a time, using top-down memoization in C#. Which of the following code snippets correctly implements this using memoization?

hard

A. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n}

B. static int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n return Ways(n - 1) + Ways(n - 2);\n}

C. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n <= 1) return n;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n}

D. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 1) return 1;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n}

Solution

1. Step 1: Analyze base cases for climbing stairs

   When n=0, there is 1 way (standing still). When n<0, no ways (0).

2. Step 2: Check memoization and recursion

   static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} correctly uses memo dictionary, checks base cases, and sums ways(n-1) and ways(n-2).

3. Step 3: Identify errors in other options

   static int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n return Ways(n - 1) + Ways(n - 2);\n} lacks memoization. static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n <= 1) return n;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} has wrong base case (n<=1 return n). static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 1) return 1;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} misses base case for n=0.

4. Final Answer:

   static Dictionary<int, int> memo = new Dictionary<int, int>();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} -> Option A

5. Quick Check:

   Base cases + memo + recursion = static Dictionary memo = new Dictionary();\nstatic int Ways(int n) {\n if (n == 0) return 1;\n if (n < 0) return 0;\n if (memo.ContainsKey(n)) return memo[n];\n memo[n] = Ways(n - 1) + Ways(n - 2);\n return memo[n];\n} [OK]

Hint: Base case n=0 returns 1; always store results in memo [OK]

Common Mistakes:

• Wrong base cases causing incorrect counts
• Not using memo causing slow recursion
• Returning n instead of 1 for base cases