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 each step.

🎯 Goal: Build a program that uses memoization with top-down dynamic programming to find the number of ways to climb n steps.

📋 What You'll Learn

Create an integer array called memo to store results for each step

Write a recursive function countWays that takes an integer n and returns the number of ways to climb n steps

Use memoization inside countWays to avoid repeated calculations

Print the number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Memoization helps optimize problems where the same calculations repeat, like counting ways to climb stairs or calculating Fibonacci numbers.

💼 Career

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

1

Create the memo array

Create an integer array called memo of size 6 and initialize all elements to -1.

DSA C

# Create an integer array called memo of size 6 and initialize all elements to -1
// Your code here

Hint

Use int memo[6] = {-1, -1, -1, -1, -1, -1}; to create and initialize the array.

2

Write the recursive function with memoization

Write a recursive function called countWays that takes an integer n and returns the number of ways to climb n steps. Use the memo array to store and reuse results. If n is 0 or 1, return 1. If memo[n] is not -1, return memo[n]. Otherwise, calculate countWays(n-1) + countWays(n-2), store it in memo[n], and return it.

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

// Write the recursive function countWays with memoization
// Your code here

int main() {
    return 0;
}

Hint

Use the base cases for 0 and 1 steps, check memo before recursion, and store results in memo.

3

Call the function for 5 steps

In the main function, call countWays with 5 and store the result in an integer variable called result.

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

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

int main() {
    // Call countWays with 5 and store in result
    // Your code here
    return 0;
}

Hint

Use int result = countWays(5); inside main.

4

Print the result

Add a printf statement in the main function to print the value of result.

DSA C

#include 

int memo[6] = {-1, -1, -1, -1, -1, -1};

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

int main() {
    int result = countWays(5);
    // Print the result
    // Your code here
    return 0;
}

Hint

Use printf("%d\n", result); to print the number of ways.