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 row by row

↓

Final answer at DP[last_item

Start by setting base cases in the table, then fill the table row by row using previous results until the final answer is found.

Execution Sample

DSA C

int knapsack(int W, int wt[], int val[], int n) {
  int dp[n+1][W+1];
  for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
      if (i == 0 || w == 0) dp[i][w] = 0;
      else 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 fills a DP table bottom-up to solve the 0/1 knapsack problem.

Execution Table

Step	Operation	Item Index (i)	Capacity (w)	Condition	DP[i][w] Value	DP Table State
1	Initialize base case	0	0	i==0 or w==0	0	[[0,0,0,0,0,0,0,0]]
2	Initialize base case	0	1	i==0 or w==0	0	[[0,0,0,0,0,0,0,0]]
3	Initialize base case	1	0	i==0 or w==0	0	[[0,0,0,0,0,0,0,0],[0,_,_,_,_,_,_,_]]
4	Check if wt[0] <= w	1	1	wt[0]=1 <= 1	max(val[0]+dp[0][0], dp[0][1])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,_,_,_,_,_,_]]
5	Check if wt[0] <= w	1	2	1 <= 2	max(1+dp[0][1], dp[0][2])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,_,_,_,_,_]]
6	Check if wt[0] <= w	1	3	1 <= 3	max(1+dp[0][2], dp[0][3])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,_,_,_,_]]
7	Check if wt[0] <= w	1	4	1 <= 4	max(1+dp[0][3], dp[0][4])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,_,_,_]]
8	Check if wt[0] <= w	1	5	1 <= 5	max(1+dp[0][4], dp[0][5])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,_,_]]
9	Check if wt[0] <= w	1	6	1 <= 6	max(1+dp[0][5], dp[0][6])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,_]]
10	Check if wt[0] <= w	1	7	1 <= 7	max(1+dp[0][6], dp[0][7])=max(1+0,0)=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1]]
11	Check if wt[1] <= w	2	1	wt[1]=3 <= 1? No	dp[1][1]=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,_,_,_,_,_,_]]
12	Check if wt[1] <= w	2	2	3 <= 2? No	dp[1][2]=1	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,_,_,_,_,_]]
13	Check if wt[1] <= w	2	3	3 <= 3? Yes	max(val[1]+dp[1][0], dp[1][3])=max(4+0,1)=4	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,_,_,_,_]]
14	Check if wt[1] <= w	2	4	3 <= 4? Yes	max(4+dp[1][1], dp[1][4])=max(4+1,1)=5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,_,_,_]]
15	Check if wt[1] <= w	2	5	3 <= 5? Yes	max(4+dp[1][2], dp[1][5])=max(4+1,1)=5	[[0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,_,_]]
16	Check if wt[1] <= w	2	6	3 <= 6? Yes	max(4+dp[1][3], dp[1][6])=max(4+1,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,_]]
17	Check if wt[1] <= w	2	7	3 <= 7? Yes	max(4+dp[1][4], dp[1][7])=max(4+1,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]]
18	Check if wt[2] <= w	3	1	wt[2]=4 <= 1? No	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,_,_,_,_,_,_]]
19	Check if wt[2] <= w	3	2	4 <= 2? No	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,_,_,_,_,_]]
20	Check if wt[2] <= w	3	3	4 <= 3? No	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,_,_,_,_]]
21	Check if wt[2] <= w	3	4	4 <= 4? Yes	max(val[2]+dp[2][0], dp[2][4])=max(5+0,5)=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,_,_,_]]
22	Check if wt[2] <= w	3	5	4 <= 5? Yes	max(5+dp[2][1], dp[2][5])=max(5+1,5)=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,_,_]]
23	Check if wt[2] <= w	3	6	4 <= 6? Yes	max(5+dp[2][2], dp[2][6])=max(5+1,5)=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,_]]
24	Check if wt[2] <= w	3	7	4 <= 7? Yes	max(5+dp[2][3], dp[2][7])=max(5+4,5)=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]]
25	Return final answer	n=3	W=7	dp[3][7]	9	Final max value is 9

💡 All items and capacities processed, final answer at dp[3][7]

Variable Tracker

Variable	Start	After Step 10	After Step 17	After Step 24	Final
i	0	1	2	3	3
w	0	7	7	7	7
dp Table	[[0,...0]]	[[0,...0],[0,1,1,1,1,1,1,1]]	[[0,...0],[0,1,1,1,1,1,1,1],[0,1,1,4,5,5,5,5]]	[[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]]	[[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]]

Key Moments - 3 Insights

Why do we initialize the first row and first column of the DP table with zeros?

Because when there are zero items (i=0) or zero capacity (w=0), the maximum value achievable is zero. This is shown in execution_table rows 1-3 where dp[i][0] and dp[0][w] are set to 0.

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

Because dp[i-1][w - wt[i-1]] represents the best value achievable with previous items and the reduced capacity after including the current item. This dependency is visible in rows like 4 and 13 where the value is calculated using dp from the previous row.

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

We cannot include the item, so we take the value from the previous row at the same capacity, dp[i-1][w]. This is shown in rows 11 and 12 where wt[1] > w and dp[i][w] = dp[i-1][w].

Visual Quiz - 3 Questions

Look at the execution_table at step 13, what is the value of dp[2][3]?

A 1

B 4

C 5

D 0

💡 Hint

Refer to execution_table row 13 under 'DP[i][w] Value' column.

At which step does the condition wt[i-1] <= w become false for the first time?

A Step 11

B Step 18

C Step 4

D Step 1

💡 Hint

Check execution_table rows where 'Condition' column shows 'No' for wt[i-1] <= w.

If the weight of the second item (wt[1]) was 2 instead of 3, how would dp[2][3] change at step 13?

A It would remain 4

B It would become 1

C It would become 5

D It would become 0

💡 Hint

Refer to how dp[i][w] is calculated using val[i-1] + dp[i-1][w - wt[i-1]] in execution_table step 13.

Concept Snapshot

Tabulation Bottom Up DP:
- Create a 2D DP table with dimensions (items+1) x (capacity+1)
- Initialize first row and column with 0 (base cases)
- Fill table row-wise: dp[i][w] = max(include current item, exclude current item)
- 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 Dynamic Programming solves problems by filling a table from the smallest subproblems up to the full problem. We start by initializing the first row and column with zeros because with zero items or zero capacity, no value can be gained. Then, for each item and capacity, we decide whether to include the item if it fits or exclude it otherwise. This decision uses previously computed values in the table. The final answer is found at the bottom-right cell of the table. This method avoids recursion and builds the solution iteratively.

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 biggest problem and break it down

Solution

1. Step 1: Understand the DP approach

   Tabulation means filling a table starting from the smallest subproblems.

2. Step 2: Compare with other methods

   Unlike recursion without storage, tabulation avoids repeated work by building up solutions.

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 tabulation with recursion without memoization
• Thinking tabulation starts from the biggest problem
• Assuming tabulation guesses solutions randomly

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[] = {0};

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

C. int dp = 100;

D. int dp(100);

Solution

1. Step 1: Check C array declaration syntax

   In C, arrays are declared with size and type, e.g., int dp[100];

2. Step 2: Identify correct initialization

   int dp[100] = {0}; declares an int array of size 100 initialized to zero, suitable for DP table.

3. Final Answer:

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

4. Quick Check:

   C arrays need size and type [OK]

Hint: Use int dp[size] = {0} for zero-initialized arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Not specifying array size
• Assigning integer to array variable

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

#include 
int main() {
    int n = 5;
    int dp[6] = {0};
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    printf("%d", dp[n]);
    return 0;
}

medium

A. 13

B. 8

C. 3

D. 5

Solution

1. Step 1: Trace DP table filling

   dp[0]=0, dp[1]=1; then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5.

2. Step 2: Identify dp[n] value

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

3. Final Answer:

   5 -> Option D

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 loop range
• Confusing dp indices with Fibonacci numbers
• Printing dp[n-1] instead of dp[n]

4. Find the error in this bottom-up DP code snippet for Fibonacci numbers:

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

medium

A. Array dp is not initialized to zero

B. Return statement should be dp[n-1]

C. Loop starts at 1 instead of 2 causing invalid access

D. Function should return void

Solution

1. Step 1: Check loop start index

   Loop starts at i=1, but dp[i-2] for i=1 is dp[-1], invalid index.

2. Step 2: Correct loop start

   Loop should start at i=2 to avoid negative index access.

3. Final Answer:

   Loop starts at 1 instead of 2 causing invalid access -> Option C

4. Quick Check:

   Loop must start at 2 to access dp[i-2] safely [OK]

Hint: Start loop at 2 for Fibonacci tabulation [OK]

Common Mistakes:

• Starting loop at 1 causing negative index
• Ignoring array bounds in DP
• Returning wrong dp index

5. Given the problem to find the minimum number of coins to make amount 7 using coins {1, 3, 4} with bottom-up DP, what is the minimum number of coins needed? Use this approach:

int coins[] = {1, 3, 4};
int amount = 7;
int dp[8];
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
    dp[i] = INT_MAX;
    for (int j = 0; j < 3; j++) {
        if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
            dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1;
        }
    }
}
printf("%d", dp[amount]);

hard

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Calculate dp values step-by-step

   dp[0]=0 For i=1: dp[1]=1 (coin 1) For i=2: dp[2]=2 (1+1) For i=3: dp[3]=1 (coin 3) For i=4: dp[4]=1 (coin 4) For i=5: dp[5]=2 (4+1) For i=6: dp[6]=2 (3+3) For i=7: dp[7]=2 (3+4)

2. Step 2: Identify minimum coins for amount 7

   Minimum coins needed for 7 is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Minimum coins for 7 = 2 [OK]

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

Common Mistakes:

• Not updating dp[i] with minimum value
• Ignoring INT_MAX checks causing wrong results
• Confusing coin values and indices