Tabulation Bottom Up DP in DSA Javascript - 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 table last cell

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

Execution Sample

DSA Javascript

const weights = [1, 3, 4];
const values = [1, 4, 5];
const W = 7;
const dp = Array(weights.length + 1).fill().map(() => Array(W + 1).fill(0));
// Fill dp bottom-up
for (let i = 1; i <= weights.length; i++) {
  for (let w = 1; w <= W; w++) {
    if (weights[i-1] <= w) {
      dp[i][w] = Math.max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]]);
    } else {
      dp[i][w] = dp[i-1][w];
    }
  }
}
console.log(dp[weights.length][W]);

This code solves the 0/1 Knapsack problem using bottom-up tabulation, filling a 2D table to find max value for capacity 7.

Execution Table

Step	Operation	Item Index (i)	Capacity (w)	DP[i][w] Computed	DP Table Row After Step
1	Initialize dp with zeros	-	-	0	[0,0,0,0,0,0,0,0]
2	i=1, w=1: weight=1 <= 1	1	1	max(dp[0][1], 1 + dp[0][0]) = 1	[0,1,0,0,0,0,0,0]
3	i=1, w=2: weight=1 <= 2	1	2	max(dp[0][2], 1 + dp[0][1]) = 1	[0,1,1,0,0,0,0,0]
4	i=1, w=3: weight=1 <= 3	1	3	max(dp[0][3], 1 + dp[0][2]) = 1	[0,1,1,1,0,0,0,0]
5	i=1, w=4: weight=1 <= 4	1	4	max(dp[0][4], 1 + dp[0][3]) = 1	[0,1,1,1,1,0,0,0]
6	i=1, w=5: weight=1 <= 5	1	5	max(dp[0][5], 1 + dp[0][4]) = 1	[0,1,1,1,1,1,0,0]
7	i=1, w=6: weight=1 <= 6	1	6	max(dp[0][6], 1 + dp[0][5]) = 1	[0,1,1,1,1,1,1,0]
8	i=1, w=7: weight=1 <= 7	1	7	max(dp[0][7], 1 + dp[0][6]) = 1	[0,1,1,1,1,1,1,1]
9	i=2, w=1: weight=3 > 1	2	1	dp[1][1] = 1	[0,1,1,1,1,1,1,1]
10	i=2, w=2: weight=3 > 2	2	2	dp[1][2] = 1	[0,1,1,1,1,1,1,1]
11	i=2, w=3: weight=3 <= 3	2	3	max(dp[1][3], 4 + dp[1][0]) = 4	[0,1,1,4,1,1,1,1]
12	i=2, w=4: weight=3 <= 4	2	4	max(dp[1][4], 4 + dp[1][1]) = 5	[0,1,1,4,5,1,1,1]
13	i=2, w=5: weight=3 <= 5	2	5	max(dp[1][5], 4 + dp[1][2]) = 5	[0,1,1,4,5,5,1,1]
14	i=2, w=6: weight=3 <= 6	2	6	max(dp[1][6], 4 + dp[1][3]) = 5	[0,1,1,4,5,5,5,1]
15	i=2, w=7: weight=3 <= 7	2	7	max(dp[1][7], 4 + dp[1][4]) = 5	[0,1,1,4,5,5,5,5]
16	i=3, w=1: weight=4 > 1	3	1	dp[2][1] = 1	[0,1,1,4,5,5,5,5]
17	i=3, w=2: weight=4 > 2	3	2	dp[2][2] = 1	[0,1,1,4,5,5,5,5]
18	i=3, w=3: weight=4 > 3	3	3	dp[2][3] = 4	[0,1,1,4,5,5,5,5]
19	i=3, w=4: weight=4 <= 4	3	4	max(dp[2][4], 5 + dp[2][0]) = 5	[0,1,1,4,5,5,5,5]
20	i=3, w=5: weight=4 <= 5	3	5	max(dp[2][5], 5 + dp[2][1]) = 6	[0,1,1,4,5,6,5,5]
21	i=3, w=6: weight=4 <= 6	3	6	max(dp[2][6], 5 + dp[2][2]) = 6	[0,1,1,4,5,6,6,5]
22	i=3, w=7: weight=4 <= 7	3	7	max(dp[2][7], 5 + dp[2][3]) = 9	[0,1,1,4,5,6,6,9]
23	End of filling dp table	-	-	-	Final dp table last row: [0,1,1,4,5,6,6,9]

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

Variable Tracker

Variable	Start	After Step 8	After Step 15	After Step 22	Final
i	0	1	2	3	3
w	0	7	7	7	7
dp[1]	[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]	[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]	[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,1,1,4,5,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 they are initialized to zero (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] and dp[i-1][w - weights[i-1]] when computing dp[i][w]?

dp[i-1][w] is the max value without current item; dp[i-1][w - weights[i-1]] + values[i-1] is with current item included (see execution_table rows 11, 12). We pick the max to ensure optimal substructure.

Why is the final answer at dp[weights.length][W]?

Because dp table rows represent items considered up to i, and columns represent capacities up to W. The last cell dp[3][7] holds the max value using all items and full capacity (see execution_table row 23).

Visual Quiz - 3 Questions

Look at the execution_table at step 12, what is the value of dp[2][4]?

A 5

B 4

C 1

D 0

💡 Hint

Check the 'DP[i][w] Computed' and 'DP Table Row After Step' columns at step 12.

At which step does the dp table first show a value greater than 4?

A Step 11

B Step 12

C Step 19

D Step 22

💡 Hint

Look at the 'DP[i][w] Computed' column and find when value 5 appears first.

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

A It would remain 4

B It would become 1

C It would become 5

D It would become 0

💡 Hint

If weight decreases, more capacity is available; check how dp[i][w] is computed using dp[i-1][w - weights[i-1]].

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(dp[i-1][w], value[i-1] + dp[i-1][w - weight[i-1]]) if weight[i-1] <= w
- Final answer at dp[items][capacity]
- Builds solution from smaller subproblems up

Full Transcript

Tabulation Bottom Up Dynamic Programming solves problems by filling a table from the smallest subproblems to the full problem. We start with a table where the first row and column are zeros, representing no items or zero capacity. Then for each item and capacity, we decide whether to include the item or not by comparing values from previous rows. This way, we build up the solution step by step. The final answer is found at the last cell of the table, representing all items considered and full capacity. This method avoids repeated calculations by storing intermediate results.

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 bottom-up approach

   Tabulation means filling a table starting from the smallest subproblems to bigger ones.

2. Step 2: Compare with other methods

   Unlike recursion without storage, tabulation 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:

   Tabulation = Bottom-up table filling [OK]

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

Common Mistakes:

• Confusing tabulation with recursion without memo
• Thinking tabulation starts from the biggest problem
• Ignoring the use of a table to store results

2. Which of the following is the correct way to initialize a tabulation array for Fibonacci numbers in JavaScript?

easy

A. const dp = [];

B. const dp = [0, 1];

C. const dp = [0, 0];

D. const dp = [1, 1];

Solution

1. Step 1: Recall Fibonacci base cases

   Fibonacci sequence starts with 0 and 1, so dp[0] = 0 and dp[1] = 1.

2. Step 2: Check initialization options

   Only const dp = [0, 1]; correctly sets dp = [0, 1] matching Fibonacci base values.

3. Final Answer:

   const dp = [0, 1]; -> Option B

4. Quick Check:

   Fibonacci base = [0,1] [OK]

Hint: Start dp with first two Fibonacci numbers [OK]

Common Mistakes:

• Starting dp with [1,1] which is incorrect base
• Initializing dp with zeros only
• Leaving dp empty without base values

3. What will be the output of the following JavaScript code using bottom-up DP to find Fibonacci number at position 5?

function fib(n) {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
console.log(fib(5));

medium

A. 3

B. 8

C. 5

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.

2. Step 2: Return dp[5]

   The function returns dp[5] which is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing index with Fibonacci value
• Returning dp[n-1] instead of dp[n]
• Starting dp with wrong base values

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

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

medium

A. dp[i - 2] causes out-of-bound error

B. dp array is not initialized

C. Return statement is missing

D. Loop starts at 1 instead of 2

Solution

1. Step 1: Analyze loop start index

   The loop starts at i=1, but dp[1] is already initialized; calculation should start at i=2.

2. Step 2: Identify impact of wrong loop start

   At i=1, dp[1] = dp[0] + dp[-1] causes dp[-1] undefined, leading to NaN.

3. Final Answer:

   Loop starts at 1 instead of 2 -> Option D

4. Quick Check:

   Loop must start at 2 to avoid invalid index [OK]

Hint: Start loop at 2 to avoid negative index [OK]

Common Mistakes:

• Starting loop at 1 causing invalid dp[-1]
• Ignoring dp initialization
• Assuming dp[-1] is zero

5. Given the problem to find the minimum number of coins to make amount 7 using coins [1, 3, 4], which bottom-up DP table entry represents the minimum coins needed for amount 5?
Assuming dp[0] = 0 and dp[i] = Infinity initially for i > 0, what is dp[5] after filling the table?

hard

A. 2

B. 3

C. 1

D. Infinity

Solution

1. Step 1: Fill dp table for amounts up to 5

   dp[0]=0; dp[1]=1 (1 coin of 1); dp[2]=2 (1+1); dp[3]=1 (coin 3); dp[4]=1 (coin 4); dp[5]=min(dp[5-1], dp[5-3], dp[5-4]) +1 = min(dp[4], dp[2], dp[1]) +1 = min(1,2,1)+1=2.

2. Step 2: Confirm dp[5] value

   Minimum coins for amount 5 is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   dp[5] = 2 coins [OK]

Hint: Check all coin options and pick minimum +1 [OK]

Common Mistakes:

• Not considering all coin choices for dp[i]
• Using wrong initial dp values
• Confusing amount with coin count