Tabulation Bottom Up DP in DSA C++ - Execution Trace

Concept Flow - Tabulation Bottom Up DP

Initialize DP table with base values

↓

Iterate over items

↓

Iterate over capacities

↓

Compute max value for current cell

↓

Fill DP table bottom-up

↓

Final answer at DP[last_item

Start with base cases, then fill the DP table row by row using previous results, ending with the final solution.

Execution Sample

DSA C++

int knapsack(int W, vector<int>& wt, vector<int>& val) {
  int n = wt.size();
  vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
  for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
      if (wt[i-1] <= w)
        dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
      else
        dp[i][w] = dp[i-1][w];
    }
  }
  return dp[n][W];
}

This code solves the 0/1 Knapsack problem using bottom-up tabulation DP.

Execution Table

Step	Operation	Item Index (i)	Capacity (w)	DP[i][w] Computed	DP Table State (row i)
1	Initialize base row	0	0 to W	0	[0, 0, 0, 0, 0, 0, 0, 0]
2	Initialize base column	0 to n	0	0	All rows start with 0 at capacity 0
3	i=1, w=1	1	1	dp[1][1] = 1 (wt=1 <= 1, max(1+dp[0][0], dp[0][1])=1)	[0, 1, 1, 1, 1, 1, 1, 1]
4	i=1, w=2	1	2	dp[1][2] = 1	[0, 1, 1, 1, 1, 1, 1, 1]
5	i=1, w=3	1	3	dp[1][3] = 1	[0, 1, 1, 1, 1, 1, 1, 1]
6	i=1, w=4	1	4	dp[1][4] = 1	[0, 1, 1, 1, 1, 1, 1, 1]
7	i=1, w=5	1	5	dp[1][5] = 1	[0, 1, 1, 1, 1, 1, 1, 1]
8	i=1, w=6	1	6	dp[1][6] = 1	[0, 1, 1, 1, 1, 1, 1, 1]
9	i=1, w=7	1	7	dp[1][7] = 1	[0, 1, 1, 1, 1, 1, 1, 1]
10	i=2, w=1	2	1	dp[2][1] = 1 (wt=3 > 1, dp[1][1])	[0, 1, 1, 1, 1, 1, 1, 1]
11	i=2, w=2	2	2	dp[2][2] = 1	[0, 1, 1, 1, 1, 1, 1, 1]
12	i=2, w=3	2	3	dp[2][3] = 4 (wt=3 <= 3, max(4+dp[1][0], dp[1][3])=4)	[0, 1, 1, 4, 4, 4, 4, 4]
13	i=2, w=4	2	4	dp[2][4] = 5 (max(4+dp[1][1], dp[1][4])=5)	[0, 1, 1, 4, 5, 5, 5, 5]
14	i=2, w=5	2	5	dp[2][5] = 5	[0, 1, 1, 4, 5, 5, 5, 5]
15	i=2, w=6	2	6	dp[2][6] = 5	[0, 1, 1, 4, 5, 5, 5, 5]
16	i=2, w=7	2	7	dp[2][7] = 5	[0, 1, 1, 4, 5, 5, 5, 5]
17	i=3, w=1	3	1	dp[3][1] = 1 (wt=4 > 1, dp[2][1])	[0, 1, 1, 4, 5, 5, 5, 5]
18	i=3, w=2	3	2	dp[3][2] = 1	[0, 1, 1, 4, 5, 5, 5, 5]
19	i=3, w=3	3	3	dp[3][3] = 4	[0, 1, 1, 4, 5, 5, 5, 5]
20	i=3, w=4	3	4	dp[3][4] = 5	[0, 1, 1, 4, 5, 5, 5, 5]
21	i=3, w=5	3	5	dp[3][5] = 6 (max(5+dp[2][1], dp[2][5])=6)	[0, 1, 1, 4, 5, 6, 6, 6]
22	i=3, w=6	3	6	dp[3][6] = 6	[0, 1, 1, 4, 5, 6, 6, 6]
23	i=3, w=7	3	7	dp[3][7] = 9 (max(5+dp[2][3], dp[2][7])=9)	[0, 1, 1, 4, 5, 6, 6, 9]
24	End	n=3	W=7	Final answer dp[3][7] = 9	DP table fully computed

💡 All items and capacities processed; final answer at dp[n][W]

Variable Tracker

Variable	Start	After Step 3	After Step 12	After Step 21	Final
i	0	1	2	3	3
w	0	1	3	5	7
dp[1][w]	[0,0,0,0,0,0,0,0]	[0,1,1,1,1,1,1,1]	[0,1,1,1,1,1,1,1]	[0,1,1,1,1,1,1,1]	[0,1,1,1,1,1,1,1]
dp[2][w]	[0,0,0,0,0,0,0,0]	[0,0,0,0,0,0,0,0]	[0,1,1,4,5,5,5,5]	[0,1,1,4,5,5,5,5]	[0,1,1,4,5,5,5,5]
dp[3][w]	[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,6,6,9]	[0,1,1,4,5,6,6,9]

Key Moments - 3 Insights

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

Row 0 and column 0 represent base cases with no items or zero capacity, so their values are zero by definition (see execution_table rows 1 and 2). We fill from i=1 and w=1 because these represent actual items and capacities.

Why do we use dp[i-1][w - wt[i-1]] when including an item?

Because dp[i-1][w - wt[i-1]] holds the best value without the current item for the reduced capacity after including the current item's weight. This is shown in execution_table rows like 3 and 12 where we add val[i-1] to dp[i-1][w - wt[i-1]].

What happens if the item's weight is more than the current capacity?

We cannot include the item, so dp[i][w] equals dp[i-1][w], the best value without this item. This is shown in execution_table rows 10 and 17.

Visual Quiz - 3 Questions

Look at the execution_table at Step 12, what is the value of dp[2][3]?

A 1

B 3

C 4

D 0

💡 Hint

Check the 'DP[i][w] Computed' column at Step 12 in execution_table.

At which step does the DP table first show a value greater than 5 in any cell?

A Step 14

B Step 21

C Step 13

D Step 24

💡 Hint

Look at the 'DP Table State (row i)' column for values >5; Step 21 shows dp[3][5] = 6.

If the weight of the second item changed from 3 to 2, how would dp[2][2] change at Step 11?

A It would increase to 4

B It would remain 1

C It would become 0

D It would decrease

💡 Hint

Refer to the logic in execution_table Step 12 where dp[2][3] = 4 because wt[1] <= w.

Concept Snapshot

Tabulation Bottom Up DP:
- Create a 2D DP table with rows = items+1, cols = capacity+1
- Initialize first row and column with 0 (base cases)
- Fill table row-wise: dp[i][w] = max(include item i or exclude it)
- Include if weight fits: val[i-1] + dp[i-1][w - wt[i-1]]
- Exclude otherwise: dp[i-1][w]
- Final answer at dp[n][W]

Full Transcript

Tabulation Bottom Up DP solves problems like 0/1 Knapsack by building a table from smaller subproblems. We start by initializing a table with zeros for no items or zero capacity. Then, for each item and capacity, we decide whether to include the item based on its weight and value, using previously computed results. This bottom-up approach fills the table row by row until the final answer is found at the bottom-right cell. Key points include starting from base cases, using previous row values for decisions, and handling cases where the item weight exceeds current capacity by excluding the item. The example code and execution table show step-by-step how the DP table is filled and how the maximum value is computed.

Practice

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

easy

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

B. Solve the problem by recursion without storing results

C. Use random guesses to find the solution

D. Start solving from the largest problem and break it down

Solution

1. Step 1: Understand bottom-up approach

   Tabulation means filling a table starting from the smallest subproblems, so we solve all smaller parts first.

2. Step 2: Compare with other methods

   Unlike recursion without memory, 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 A

4. Quick Check:

   Bottom-up DP = Build table from small to big [OK]

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

Common Mistakes:

• Confusing bottom-up with recursion without memoization
• Thinking it starts from the largest problem
• Ignoring the use of a table to store results

2. Which of the following is the correct way to declare a DP table for Fibonacci numbers using tabulation in C++?

easy

A. int dp[]; dp[1] = 1;

B. int dp[100] = {0}; dp[1] = 1;

C. int dp[100]; dp[0] = 1;

D. int dp[100] = {1}; dp[2] = 1;

Solution

1. Step 1: Check array initialization

   int dp[100] = {0}; dp[1] = 1; initializes dp with zeros and sets dp[1] = 1, which is correct for Fibonacci base cases.

2. Step 2: Identify errors in other options

   int dp[]; dp[1] = 1; has no size for dp array, invalid in C++. int dp[100]; dp[0] = 1; sets dp[0] = 1 which is incorrect base case. int dp[100] = {1}; dp[2] = 1; initializes dp with 1 at dp[0], which is wrong.

3. Final Answer:

   int dp[100] = {0}; dp[1] = 1; -> Option B

4. Quick Check:

   Correct base initialization = int dp[100] = {0}; dp[1] = 1; [OK]

Hint: Initialize dp array with zeros and set base cases explicitly [OK]

Common Mistakes:

• Not specifying array size
• Wrong base case initialization
• Assuming default values without initialization

3. What will be the output of the following C++ code using bottom-up DP to find the 5th Fibonacci number?

int fib(int n) {
  int dp[6] = {0};
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

int main() {
  std::cout << fib(5);
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Trace dp array filling

   dp[0]=0, dp[1]=1; then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5 by adding previous two.

2. Step 2: Return dp[5]

   dp[5] is 5, so output is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Fibonacci(5) = 5 [OK]

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

Common Mistakes:

• Off-by-one errors in indexing
• Confusing dp[0] and dp[1] values
• Returning wrong dp index

4. Identify the error in this bottom-up DP code for computing factorial of n:

int factorial(int n) {
  int dp[100];
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    dp[i] = dp[i-1] * i;
  }
  return dp[n];
}

medium

A. dp array not initialized to zero

B. Loop should start from i = 0

C. dp array size might be too small for large n

D. No error, code is correct

Solution

1. Step 1: Check dp array size

   dp array size is fixed at 100, so if n > 99, dp[i] access is out of bounds causing error.

2. Step 2: Analyze other parts

   Initialization and loop logic are correct; loop starts at 1 and dp[0] = 1 is base case.

3. Final Answer:

   dp array size might be too small for large n -> Option C

4. Quick Check:

   Array size must fit n [OK]

Hint: Ensure dp array size >= n to avoid overflow [OK]

Common Mistakes:

• Assuming dp size is always enough
• Starting loop at wrong index
• Ignoring base case initialization

5. Given the problem to find the minimum number of coins to make amount 11 using coins {1, 3, 5}, which bottom-up DP table entry dp[11] will hold after running this code?

int coins[] = {1, 3, 5};
int n = 11;
int dp[12];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
  dp[i] = 1000; // large number
  for (int c : coins) {
    if (i - c >= 0) {
      dp[i] = std::min(dp[i], dp[i-c] + 1);
    }
  }
}
std::cout << dp[n];

hard

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Understand DP logic for coin change

   dp[i] stores minimum coins for amount i. For 11, check coins 1,3,5 and pick minimum.

2. Step 2: Calculate dp values up to 11

   dp[0]=0; dp[1]=1; dp[2]=2; dp[3]=1; dp[4]=2; dp[5]=1; dp[6]=2; dp[7]=3; dp[8]=2; dp[9]=3; dp[10]=2; dp[11]=3 (e.g., 5+5+1 or 3+3+5)

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Minimum coins for 11 = 3 [OK]

Hint: Build dp from 0 to n, pick min coins at each step [OK]

Common Mistakes:

• Not initializing dp[0] = 0
• Using max int instead of large number
• Forgetting to check i - coin >= 0