Tabulation Bottom Up DP in DSA Rust - Execution Trace

Concept Flow - Tabulation Bottom Up DP

Initialize DP table with zeros

↓

Iterate over items

↓

Iterate over capacities

↓

Check if item fits

↓

Update DP cell

↓

Repeat for all items and capacities

↓

Final answer in DP table last cell

Start with a zero-filled table, fill it row by row considering each item and capacity, updating values based on whether the item fits or not, ending with the optimal solution at the last cell.

Execution Sample

DSA Rust

let weights = [1, 3, 4];
let values = [1, 4, 5];
let capacity = 7;
let mut dp = vec![vec![0; capacity + 1]; weights.len() + 1];
for i in 1..=weights.len() {
    for w in 0..=capacity {
        if weights[i - 1] <= w {
            dp[i][w] = std::cmp::max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
        } else {
            dp[i][w] = dp[i - 1][w];
        }
    }
}

This code creates a DP table and fills it bottom-up for the 0/1 knapsack problem with given weights, values, and capacity.

Execution Table

Step	Operation	Item Index (i)	Capacity (w)	DP[i][w] Value	Action	DP Table Row State
1	Initialize DP table	-	-	All zeros	Create 4x8 table filled with 0	[[0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
2	i=1, w=0	1	0	0	Weight 1 > capacity 0? Yes, copy dp[0][0]	[[0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
3	i=1, w=1	1	1	1	Weight 1 <= 1, max(dp[0][1], value[0]+dp[0][0])=max(0,1+0)=1	[[0,0,0,0,0,0,0,0], [0,1,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
4	i=1, w=2	1	2	1	Weight 1 <= 2, max(dp[0][2],1+dp[0][1])=max(0,1+0)=1	[[0,0,0,0,0,0,0,0], [0,1,1,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
5	i=1, w=3	1	3	1	Weight 1 <= 3, max(dp[0][3],1+dp[0][2])=max(0,1+0)=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
6	i=1, w=4	1	4	1	Weight 1 <= 4, max(dp[0][4],1+dp[0][3])=max(0,1+0)=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
7	i=1, w=5	1	5	1	Weight 1 <= 5, max(dp[0][5],1+dp[0][4])=max(0,1+0)=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
8	i=1, w=6	1	6	1	Weight 1 <= 6, max(dp[0][6],1+dp[0][5])=max(0,1+0)=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
9	i=1, w=7	1	7	1	Weight 1 <= 7, max(dp[0][7],1+dp[0][6])=max(0,1+0)=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
10	i=2, w=0	2	0	0	Weight 3 > 0? Yes, copy dp[1][0]	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
11	i=2, w=1	2	1	1	Weight 3 > 1? Yes, copy dp[1][1]=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,0,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
12	i=2, w=2	2	2	1	Weight 3 > 2? Yes, copy dp[1][2]=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,0,0,0,0,0], [0,0,0,0,0,0,0,0]]
13	i=2, w=3	2	3	4	Weight 3 <= 3, max(dp[1][3],4+dp[1][0])=max(1,4+0)=4	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,0,0,0,0], [0,0,0,0,0,0,0,0]]
14	i=2, w=4	2	4	5	Weight 3 <= 4, max(dp[1][4],4+dp[1][1])=max(1,4+1)=5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,0,0,0], [0,0,0,0,0,0,0,0]]
15	i=2, w=5	2	5	5	Weight 3 <= 5, max(dp[1][5],4+dp[1][2])=max(1,4+1)=5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,0,0], [0,0,0,0,0,0,0,0]]
16	i=2, w=6	2	6	5	Weight 3 <= 6, max(dp[1][6],4+dp[1][3])=max(1,4+1)=5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,0], [0,0,0,0,0,0,0,0]]
17	i=2, w=7	2	7	5	Weight 3 <= 7, max(dp[1][7],4+dp[1][4])=max(1,4+1)=5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,0,0,0,0,0,0,0]]
18	i=3, w=0	3	0	0	Weight 4 > 0? Yes, copy dp[2][0]	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,0,0,0,0,0,0,0]]
19	i=3, w=1	3	1	1	Weight 4 > 1? Yes, copy dp[2][1]=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,0,0,0,0,0,0]]
20	i=3, w=2	3	2	1	Weight 4 > 2? Yes, copy dp[2][2]=1	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,0,0,0,0,0]]
21	i=3, w=3	3	3	4	Weight 4 > 3? Yes, copy dp[2][3]=4	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,0,0,0,0]]
22	i=3, w=4	3	4	5	Weight 4 <= 4, max(dp[2][4],5+dp[2][0])=max(5,5+0)=5	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,0,0,0]]
23	i=3, w=5	3	5	6	Weight 4 <= 5, max(dp[2][5],5+dp[2][1])=max(5,5+1)=6	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,6,0,0]]
24	i=3, w=6	3	6	6	Weight 4 <= 6, max(dp[2][6],5+dp[2][2])=max(5,5+1)=6	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,6,6,0]]
25	i=3, w=7	3	7	9	Weight 4 <= 7, max(dp[2][7],5+dp[2][3])=max(5,5+4)=9	[[0,0,0,0,0,0,0,0], [0,1,1,1,1,1,1,1], [0,1,1,4,5,5,5,5], [0,1,1,4,5,6,6,9]]

💡 All items and capacities processed; final answer is dp[3][7] = 9

Variable Tracker

Variable	Start	After Step 1	After Step 9	After Step 17	After Step 25 (Final)
dp table	empty	zeros 4x8	row 1 filled with values for item 1	row 2 filled with values for item 2	full table with all items processed
i (item index)	0	1	1	2	3
w (capacity)	0	7	7	7	7

Key Moments - 3 Insights

Why do we start filling the DP table from i=1 and w=0 instead of i=0?

Row i=0 represents no items, so dp[0][w] is always 0. We start from i=1 to consider the first item. This is shown in execution_table rows 2 and 3 where i=1 starts filling values.

Why do we copy the previous row's value when the item weight is greater than current capacity?

Because the current item cannot fit, so the best value remains the same as without this item. This is seen in execution_table rows 11 and 12 where weight 3 > capacity 1 or 2, so dp[i][w] = dp[i-1][w].

How do we decide between including or excluding an item in the DP table?

We take the maximum of excluding the item (dp[i-1][w]) and including it (value + dp[i-1][w - weight]). This decision is shown in rows like 13 and 23 where max is chosen.

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what is the DP[i][w] value and why?

A 4, because item fits and including it gives better value

B 1, because item does not fit

C 0, because no items considered yet

D 5, because previous row had 5

💡 Hint

Check execution_table row 13 where i=2, w=3, and see the max calculation.

At which step does the DP table first show a value greater than 1?

A Step 3

B Step 13

C Step 23

D Step 25

💡 Hint

Look at the DP[i][w] Value column in execution_table rows for values >1.

If the capacity was reduced to 5, what would be the final DP value at dp[3][5]?

A 5

B 9

C 6

D 4

💡 Hint

Refer to execution_table row 23 where i=3, w=5, dp value is 6.

Concept Snapshot

Tabulation Bottom Up DP:
- Create a 2D DP table with rows = items+1, cols = capacity+1
- Initialize first row and column with zeros
- For each item i and capacity w:
  - If item weight <= w, dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i-1][w - weight[i-1]])
  - Else dp[i][w] = dp[i-1][w]
- Final answer at dp[items][capacity]

Full Transcript

Tabulation Bottom Up DP builds a table starting with zeros. We fill it row by row for each item and capacity. If the item fits, we choose the best between including or excluding it. If it doesn't fit, we copy the previous best. The final answer is in the last cell of the table. This method avoids recursion by solving smaller problems first and using their results to solve bigger problems.

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