Tabulation Bottom Up DP in DSA Rust

Mental Model

Solve a big problem by first solving all smaller problems and storing their answers in a table. Then build up to the final answer step by step.

Analogy: Imagine climbing stairs where you know how to get to each step from the bottom. You start at step 0 and move up, remembering how you got there, so you don't have to guess or repeat steps.

Index: 0  1  2  3  4  5
Table: [0][ ][ ][ ][ ][ ]
          ↑
Start filling from the bottom (index 0) upwards.

Dry Run Walkthrough

Input: Find the 5th Fibonacci number using bottom-up tabulation

Goal: Calculate Fibonacci(5) by filling a table from the smallest subproblems up to 5

Step 1: Initialize table with base cases: fib[0] = 0, fib[1] = 1

fib: [0, 1, _, _, _, _]

Why: Base cases are known and needed to build bigger answers

Step 2: Calculate fib[2] = fib[1] + fib[0] = 1 + 0 = 1

fib: [0, 1, 1, _, _, _]

Why: Use previous results to find next Fibonacci number

Step 3: Calculate fib[3] = fib[2] + fib[1] = 1 + 1 = 2

fib: [0, 1, 1, 2, _, _]

Why: Build on known smaller results

Step 4: Calculate fib[4] = fib[3] + fib[2] = 2 + 1 = 3

fib: [0, 1, 1, 2, 3, _]

Why: Continue building up the table

Step 5: Calculate fib[5] = fib[4] + fib[3] = 3 + 2 = 5

fib: [0, 1, 1, 2, 3, 5]

Why: Final answer is ready after filling the table

Result:

fib: [0, 1, 1, 2, 3, 5]
Answer: 5

Annotated Code

DSA Rust

fn fibonacci(n: usize) -> usize {
    if n == 0 { return 0; }
    let mut fib = vec![0; n + 1];
    fib[0] = 0; // base case
    fib[1] = 1; // base case
    for i in 2..=n {
        fib[i] = fib[i - 1] + fib[i - 2]; // build from smaller subproblems
    }
    fib[n] // return final answer
}

fn main() {
    let n = 5;
    let result = fibonacci(n);
    println!("Fibonacci({}) = {}", n, result);
}

fib[0] = 0; // base case

Set first known Fibonacci number

fib[1] = 1; // base case

Set second known Fibonacci number

for i in 2..=n {

Loop from 2 up to n to fill table

fib[i] = fib[i - 1] + fib[i - 2]; // build from smaller subproblems

Calculate current Fibonacci using previous two

fib[n] // return final answer

Return the computed Fibonacci number

Output

Fibonacci(5) = 5

Complexity Analysis

Time: O(n) because we fill the table once from 0 to n

Space: O(n) because we store all Fibonacci numbers up to n in the table

vs Alternative: Compared to naive recursion which is exponential O(2^n), tabulation is much faster and avoids repeated work

Edge Cases

n = 0

Returns 0 immediately without looping

DSA Rust

if n == 0 { return 0; }

n = 1

Returns 1 after setting base cases

DSA Rust

fib[1] = 1; // base case

When to Use This Pattern

When you see a problem that can be broken into smaller overlapping subproblems and you want to avoid repeated work, use bottom-up tabulation to build answers from the smallest cases up.

Common Mistakes

Mistake: Trying to compute the answer recursively without storing results, causing repeated calculations.
Fix: Use a table (array) to store results of smaller problems and fill it iteratively.

Mistake: Not initializing base cases in the table before starting the loop.
Fix: Always set known base cases before building up the table.

Summary

It solves problems by filling a table from the smallest subproblems up to the final solution.

Use it when a problem can be split into smaller overlapping parts and you want to avoid repeated work.

The key is to start from the base cases and build up answers step by step in a table.

Practice

1. What is the main idea behind Tabulation Bottom Up DP in dynamic programming?

easy

A. Use random guesses to find the solution

B. Solve the problem by recursion without storing results

C. Start solving from the main problem and break it down recursively

D. Build a table from the smallest subproblems up to the main problem

Solution

1. Step 1: Understand bottom-up approach

   Tabulation means filling a table starting from the smallest subproblems, building up to the final answer.

2. Step 2: Compare with other methods

   Unlike recursion without memoization, bottom-up avoids repeated work by storing results in a table.

3. Final Answer:

   Build a table from the smallest subproblems up to the main problem -> Option D

4. Quick Check:

   Tabulation = Bottom-up DP [OK]

Hint: Think: solve small parts first, then bigger ones [OK]

Common Mistakes:

• Confusing bottom-up with top-down recursion
• Ignoring the use of a table to store results
• Thinking tabulation uses random guesses

2. Which of the following Rust code snippets correctly initializes a vector for tabulation with size 5 and all zeros?

easy

A. let mut dp = vec![0; 5];

B. let dp = vec![0;];

C. let mut dp = Vec::new(5);

D. let dp = vec!(5, 0);

Solution

1. Step 1: Check Rust vector initialization syntax

   To create a vector of size 5 filled with zeros, use vec![0; 5].

2. Step 2: Analyze options

   let mut dp = vec![0; 5]; uses correct syntax. let dp = vec![0;]; is missing size. let mut dp = Vec::new(5); is invalid because Vec::new() takes no size. let dp = vec!(5, 0); uses wrong macro syntax.

3. Final Answer:

   let mut dp = vec![0; 5]; -> Option A

4. Quick Check:

   vec![value; size] creates vector [OK]

Hint: Use vec![value; size] to initialize vectors [OK]

Common Mistakes:

• Using Vec::new() with size argument
• Incorrect macro syntax with vec!()
• Omitting size in vector initialization

3. What will be the output of the following Rust code using bottom-up DP to compute Fibonacci numbers?

fn fib(n: usize) -> usize {
    let mut dp = vec![0; n + 1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n]
}

fn main() {
    println!("{}", fib(6));
}

medium

A. 13

B. 5

C. 8

D. 21

Solution

1. Step 1: Trace Fibonacci calculation for n=6

   dp array fills as: dp[0]=0, dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5, dp[6]=8.

2. Step 2: Output dp[6]

   The function returns dp[6] which is 8.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   fib(6) = 8 [OK]

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

Common Mistakes:

• Starting dp[1] as 0 instead of 1
• Off-by-one errors in loop range
• Confusing dp indices with Fibonacci numbers

4. Identify the error in this Rust bottom-up DP code for computing factorial and select the fix:

fn factorial(n: usize) -> usize {
    let mut dp = vec![1; n + 1];
    for i in 1..=n {
        dp[i] = dp[i - 1] * i;
    }
    dp[n]
}

fn main() {
    println!("{}", factorial(5));
}

medium

A. Initialize dp with zeros instead of ones

B. Change loop to start from 2 instead of 1

C. Use dp[i] = dp[i] * i instead of dp[i - 1] * i

D. Return dp[n-1] instead of dp[n]

Solution

1. Step 1: Analyze initialization and loop

   dp[0] = 1 is correct for factorial base case. Loop starting at 1 causes dp[1] = dp[0] * 1 = 1, which is correct but redundant.

2. Step 2: Fix loop start to avoid redundant calculation

   Starting loop at 2 avoids unnecessary multiplication and matches factorial definition better.

3. Final Answer:

   Change loop to start from 2 instead of 1 -> Option B

4. Quick Check:

   Factorial loop starts at 2 [OK]

Hint: Factorial base case at dp[0], loop from 2 [OK]

Common Mistakes:

• Starting loop at 1 causing redundant calculation
• Initializing dp with zeros breaking multiplication
• Returning wrong dp index

5. You want to find the minimum number of coins needed to make amount 7 using coins [1, 3, 4] with bottom-up DP in Rust. Which code snippet correctly implements this?

hard

A. let mut dp = vec![usize::MAX; 8]; dp[0] = 0; for i in 1..=7 { for &coin in &[1,3,4] { if i >= coin && dp[i - coin] != usize::MAX { dp[i] = dp[i].min(dp[i - coin] + 1); } } } dp[7]

B. let mut dp = vec![0; 8]; for i in 1..=7 { for &coin in &[1,3,4] { dp[i] += dp[i - coin]; } } dp[7]

C. let mut dp = vec![usize::MAX; 7]; dp[0] = 0; for i in 1..7 { for &coin in &[1,3,4] { if i > coin { dp[i] = dp[i - coin] + 1; } } } dp[6]

D. let mut dp = vec![0; 7]; dp[0] = 1; for i in 1..7 { for &coin in &[1,3,4] { if i >= coin { dp[i] = dp[i - coin] + 1; } } } dp[6]

Solution

1. Step 1: Initialize dp with max values and base case

   dp size must be 8 for amounts 0 to 7. dp[0] = 0 means zero coins needed for amount 0.

2. Step 2: Update dp with minimum coins for each amount

   For each amount i, check all coins. If coin fits and previous dp is valid, update dp[i] with minimum coins.

3. Step 3: Return dp[7]

   dp[7] holds minimum coins needed for amount 7.

4. Final Answer:

   let mut dp = vec![usize::MAX; 8]; dp[0] = 0; for i in 1..=7 { for &coin in &[1,3,4] { if i >= coin && dp[i - coin] != usize::MAX { dp[i] = dp[i].min(dp[i - coin] + 1); } } } dp[7] -> Option A

5. Quick Check:

   Minimum coins DP uses min and checks valid previous states [OK]

Hint: Use usize::MAX and min() to track minimum coins [OK]

Common Mistakes:

• Incorrect dp size causing index errors
• Not checking if previous dp value is valid
• Adding instead of taking minimum coins