Memoization Top Down DP in DSA Rust - 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 Rust program that uses memoization with a top-down dynamic programming approach to find the number of ways to climb n steps.

📋 What You'll Learn

Create a function called count_ways that takes n: usize and a mutable reference to a vector memo: &mut Vec>.

Use memo to store results for each step to avoid repeated calculations.

Initialize memo with None values for all steps from 0 to n.

Call count_ways with the total steps n and the memo vector.

Print the number of ways to climb n steps.

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world problems where repeated calculations happen, such as route planning, resource allocation, and game AI.

💼 Career

Understanding memoization and dynamic programming is essential for software engineers working on optimization problems, algorithm design, and performance-critical applications.

1

Create the memo vector for storing results

Create a mutable vector called memo with n + 1 elements, all set to None. Use let n = 5; for the number of steps.

DSA Rust

let n = 5;
// Your code here

Hint

Use vec![None; n + 1] to create a vector with None values.

2

Define the count_ways function with memoization

Define a function called count_ways that takes n: usize and memo: &mut Vec>. Inside, return 1 if n is 0 or 1. If memo[n] has a value, return it. Otherwise, recursively call count_ways(n - 1, memo) and count_ways(n - 2, memo), sum the results, store in memo[n], and return it.

DSA Rust

let n = 5;
let mut memo: Vec> = vec![None; n + 1];

// Your code here

Hint

Use if let Some(value) = memo[n] to check if the result is already computed.

3

Call count_ways with n and memo

Call the function count_ways with arguments n and &mut memo, and store the result in a variable called result.

DSA Rust

let n = 5;
let mut memo: Vec> = vec![None; n + 1];

fn count_ways(n: usize, memo: &mut Vec>) -> usize {
    if n == 0 || n == 1 {
        return 1;
    }
    if let Some(value) = memo[n] {
        return value;
    }
    let ways = count_ways(n - 1, memo) + count_ways(n - 2, memo);
    memo[n] = Some(ways);
    ways
}

// Your code here

Hint

Call count_ways with n and &mut memo and save the output.

4

Print the result

Print the value of result using println!.

DSA Rust

let n = 5;
let mut memo: Vec> = vec![None; n + 1];

fn count_ways(n: usize, memo: &mut Vec>) -> usize {
    if n == 0 || n == 1 {
        return 1;
    }
    if let Some(value) = memo[n] {
        return value;
    }
    let ways = count_ways(n - 1, memo) + count_ways(n - 2, memo);
    memo[n] = Some(ways);
    ways
}

let result = count_ways(n, &mut memo);

// Your code here

Hint

Use println!("{}", result); to print the number of ways.

Practice

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

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 memory usage by deleting variables

Solution

1. Step 1: Understand memoization role

   Memoization saves 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 describes this purpose correctly. Sorting, converting recursion, or deleting variables 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
• Thinking memoization reduces memory by deleting data
• Believing memoization changes recursion to iteration

2. Which of the following Rust code snippets correctly declares a memoization cache for a function with input type usize and output type usize?

easy

A. let memo: Vec<usize> = Vec::new();

B. let memo = HashMap::new();

C. let mut memo: Vec = vec![None; n + 1];

D. let mut memo: Vec<usize> = vec![0; n];

Solution

1. Step 1: Identify correct memo type

   Memoization cache should store Option<usize> to mark computed or not, initialized with None.

2. Step 2: Check each option

   let mut memo: Vec = vec![None; n + 1]; uses Vec with None values, correct for memoization. let memo = HashMap::new(); is a HashMap but missing mut and initialization syntax. let memo: Vec<usize> = Vec::new(); lacks Option type. let mut memo: Vec<usize> = vec![0; n]; uses usize with zeros, which can't distinguish computed or not.

3. Final Answer:

   let mut memo: Vec = vec![None; n + 1]; -> Option C

4. Quick Check:

   Memo cache = Vec with None [OK]

Hint: Use Option type to mark uncomputed states [OK]

Common Mistakes:

• Using Vec<usize> without Option to track computed
• Not making memo mutable
• Incorrect initialization of HashMap

3. Consider this Rust function using memoization to compute Fibonacci numbers:

fn fib(n: usize, memo: &mut Vec) -> usize {
    if n <= 1 {
        return n;
    }
    if let Some(val) = memo[n] {
        return val;
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = Some(result);
    result
}

fn main() {
    let n = 5;
    let mut memo = vec![None; n + 1];
    println!("{}", fib(n, &mut memo));
}

What is the output when this code runs?

medium

A. 8

B. 5

C. 3

D. 13

Solution

1. Step 1: Understand Fibonacci calculation

   fib(5) = fib(4) + fib(3). Calculating recursively with memoization avoids repeated work.

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 fib(5) with fib(6)
• Forgetting zero-based indexing
• Ignoring memoization effect

4. This Rust code tries to memoize the factorial function but has a bug:

fn fact(n: usize, memo: &mut Vec) -> usize {
    if n == 0 {
        return 1;
    }
    if memo[n].is_some() {
        return memo[n].unwrap();
    }
    let result = n * fact(n - 1, memo);
    memo[n] = Some(result);
    result
}

fn main() {
    let n = 5;
    let mut memo = vec![None; n];
    println!("{}", fact(n, &mut memo));
}

What is the bug causing a runtime error?

medium

A. The memo vector size is too small causing index out of bounds

B. The base case should return 0 instead of 1

C. The function does not update memo correctly

D. The function should not use recursion

Solution

1. Step 1: Check memo vector size

   Memo is created with size n (5), but fact accesses memo[n], which is memo[5], out of bounds since indices go 0 to 4.

2. Step 2: Identify cause of runtime error

   Accessing memo[5] causes panic due to index out of bounds. The vector should be size n+1 to include index 5.

3. Final Answer:

   The memo vector size is too small causing index out of bounds -> Option A

4. Quick Check:

   Vector size < needed index = runtime error [OK]

Hint: Memo size must cover all indices used [OK]

Common Mistakes:

• Ignoring vector size when indexing
• Changing base case incorrectly
• Thinking recursion is the problem

5. You want to use top-down memoization in Rust to count the number of ways to climb a staircase of n steps, taking 1 or 2 steps at a time. Which of these implementations correctly applies memoization to avoid repeated calculations?

fn climb(n: usize, memo: &mut Vec) -> usize {
    if n == 0 {
        return 1;
    }
    if n < 0 {
        return 0;
    }
    if let Some(val) = memo[n] {
        return val;
    }
    let ways = climb(n - 1, memo) + climb(n - 2, memo);
    memo[n] = Some(ways);
    ways
}

fn main() {
    let n = 4;
    let mut memo = vec![None; n + 1];
    println!("{}", climb(n, &mut memo));
}

hard

A. Incorrect because it does not handle negative indices safely

B. Incorrect because it uses iteration instead of recursion

C. Incorrect because memo vector is not mutable

D. Correct implementation with proper base cases and memo usage

Solution

1. Step 1: Check base cases and recursion

   Base cases handle n == 0 (1 way) and n < 0 (0 ways), which is correct for counting ways.

2. Step 2: Verify memoization usage

   Memo vector is mutable and stores Option<usize>. It checks memo[n] before recursion and stores result after calculation.

3. Step 3: Confirm no unsafe indexing

   Negative n returns 0 before indexing memo, so no out-of-bounds access.

4. Final Answer:

   Correct implementation with proper base cases and memo usage -> Option D

5. Quick Check:

   Base cases + memo check = correct memoization [OK]

Hint: Check base cases and memo before recursion [OK]

Common Mistakes:

• Not handling negative n before memo access
• Forgetting to make memo mutable
• Using iteration instead of recursion in top-down DP