Tabulation Bottom Up DP in DSA Typescript - 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 by setting base cases in the table, then fill each cell by checking if including the current item improves the value, moving from smaller subproblems to bigger ones.

Execution Sample

DSA Typescript

const weights = [1, 3, 4];
const values = [1, 4, 5];
const W = 7;
const dp = Array(weights.length + 1).fill(0).map(() => Array(W + 1).fill(0));
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], dp[i-1][w - weights[i-1]] + values[i-1]);
    } else {
      dp[i][w] = dp[i-1][w];
    }
  }
}

This code fills a DP table to solve the 0/1 Knapsack problem using bottom-up tabulation.

Execution Table

Step	Operation	Item Index (i)	Capacity (w)	Condition (weights[i-1] <= w)	DP[i][w] Computed	DP Table Row i State
1	Initialize base row	0	0 to 7	N/A	0	[0,0,0,0,0,0,0,0]
2	i=1, w=1	1	1	1 <= 1: true	max(dp[0][1], dp[0][0] + 1) = max(0,0+1)=1	[0,1,0,0,0,0,0,0]
3	i=1, w=2	1	2	1 <= 2: true	max(dp[0][2], dp[0][1] + 1) = max(0,0+1)=1	[0,1,1,0,0,0,0,0]
4	i=1, w=3	1	3	1 <= 3: true	max(dp[0][3], dp[0][2] + 1) = max(0,0+1)=1	[0,1,1,1,0,0,0,0]
5	i=1, w=4	1	4	1 <= 4: true	max(dp[0][4], dp[0][3] + 1) = max(0,0+1)=1	[0,1,1,1,1,0,0,0]
6	i=1, w=5	1	5	1 <= 5: true	max(dp[0][5], dp[0][4] + 1) = max(0,0+1)=1	[0,1,1,1,1,1,0,0]
7	i=1, w=6	1	6	1 <= 6: true	max(dp[0][6], dp[0][5] + 1) = max(0,0+1)=1	[0,1,1,1,1,1,1,0]
8	i=1, w=7	1	7	1 <= 7: true	max(dp[0][7], dp[0][6] + 1) = max(0,0+1)=1	[0,1,1,1,1,1,1,1]
9	i=2, w=1	2	1	3 <= 1: false	dp[1][1] = 1	[0,1,1,1,1,1,1,1]
10	i=2, w=2	2	2	3 <= 2: false	dp[1][2] = 1	[0,1,1,1,1,1,1,1]
11	i=2, w=3	2	3	3 <= 3: true	max(dp[1][3], dp[1][0] + 4) = max(1,0+4)=4	[0,1,1,4,1,1,1,1]
12	i=2, w=4	2	4	3 <= 4: true	max(dp[1][4], dp[1][1] + 4) = max(1,1+4)=5	[0,1,1,4,5,1,1,1]
13	i=2, w=5	2	5	3 <= 5: true	max(dp[1][5], dp[1][2] + 4) = max(1,1+4)=5	[0,1,1,4,5,5,1,1]
14	i=2, w=6	2	6	3 <= 6: true	max(dp[1][6], dp[1][3] + 4) = max(1,4+4)=8	[0,1,1,4,5,5,8,1]
15	i=2, w=7	2	7	3 <= 7: true	max(dp[1][7], dp[1][4] + 4) = max(1,5+4)=9	[0,1,1,4,5,5,8,9]
16	i=3, w=1	3	1	4 <= 1: false	dp[2][1] = 1	[0,1,1,4,5,5,8,9]
17	i=3, w=2	3	2	4 <= 2: false	dp[2][2] = 1	[0,1,1,4,5,5,8,9]
18	i=3, w=3	3	3	4 <= 3: false	dp[2][3] = 4	[0,1,1,4,5,5,8,9]
19	i=3, w=4	3	4	4 <= 4: true	max(dp[2][4], dp[2][0] + 5) = max(5,0+5)=5	[0,1,1,4,5,5,8,9]
20	i=3, w=5	3	5	4 <= 5: true	max(dp[2][5], dp[2][1] + 5) = max(5,1+5)=6	[0,1,1,4,5,6,8,9]
21	i=3, w=6	3	6	4 <= 6: true	max(dp[2][6], dp[2][2] + 5) = max(8,1+5)=8	[0,1,1,4,5,6,8,9]
22	i=3, w=7	3	7	4 <= 7: true	max(dp[2][7], dp[2][3] + 5) = max(9,4+5)=9	[0,1,1,4,5,6,8,9]

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

Variable Tracker

Variable	Start	After Step 8	After Step 15	After Step 22 (Final)
i (item index)	0	1	2	3
w (capacity)	0	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]
dp[2]	[0,0,0,0,0,0,0,0]	[0,1,1,1,1,1,1,1]	[0,1,1,4,5,5,8,9]	[0,1,1,4,5,5,8,9]
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,8,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. Filling starts from i=1 and w=1 to build on these base cases, as shown in execution_table rows 2 and 3.

Why do we use dp[i-1][w - weights[i-1]] + values[i-1] when weights[i-1] <= w?

This expression means including the current item: we add its value to the best solution for the remaining capacity (w - weights[i-1]) without this item (i-1). This is the core of the bottom-up approach, seen in execution_table rows like 11 and 20.

Why do we take the max between including and excluding the current item?

We want the best value possible. Including the item might increase value, but if it doesn't fit or is worse, excluding it is better. The max function ensures we pick the best option, as shown in many steps like 11 and 20.

Visual Quiz - 3 Questions

Look at the execution_table at step 11. What is the value of dp[2][3]?

A 1

B 4

C 0

D 5

💡 Hint

Check the 'DP[i][w] Computed' column at step 11 in the execution_table.

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

A Step 20

B Step 18

C Step 19

D Step 22

💡 Hint

Look at the 'DP Table Row i State' column for row 3 in the execution_table from step 18 to 22.

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

A It would become 5

B It would remain 1

C It would become 4

D It would become 0

💡 Hint

If weights[1] <= w at w=2, dp[2][2] would be max of excluding or including item 2, see step 11 logic.

Concept Snapshot

Tabulation Bottom Up DP:
- Create a 2D DP table with items as rows and capacities as columns.
- Initialize first row and column with zeros (base cases).
- Fill table row by row, capacity by capacity.
- For each cell, choose max of excluding or including current item.
- Final answer at dp[number_of_items][max_capacity].

Full Transcript

Tabulation Bottom Up Dynamic Programming solves problems by building a table from smaller to bigger subproblems. We start with base cases where no items or zero capacity means zero value. Then, for each item and capacity, we decide whether to include the item or not by comparing values. This fills the table step by step until the final answer is found at the bottom-right cell. The example code and table show this process clearly, with each step updating the DP table based on previous results.

Practice

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

easy

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

B. Solve the problem by dividing it into two halves recursively

C. Use recursion with memoization to avoid repeated work

D. Randomly guess answers and check correctness

Solution

1. Step 1: Understand Tabulation approach

   Tabulation means filling a table starting from the smallest subproblems, moving upwards.

2. Step 2: Compare with other methods

   Unlike recursion with memoization, tabulation solves subproblems iteratively in order.

3. Final Answer:

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

4. Quick Check:

   Tabulation = Bottom Up DP [OK]

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

Common Mistakes:

• Confusing tabulation with recursion
• Thinking tabulation guesses answers
• Mixing memoization with tabulation

2. Which of the following is the correct TypeScript syntax to initialize a DP array of size n+1 with zeros for tabulation?

easy

A. const dp = new Array(n+1).fill(0);

B. const dp = Array().map(() => 0);

C. const dp = new Array(n).fill(null);

D. const dp = Array.fill(n+1, 0);

Solution

1. Step 1: Check correct array initialization

   Using new Array(n+1).fill(0) creates an array of length n+1 filled with zeros.

2. Step 2: Identify incorrect options

   const dp = Array().map(() => 0); uses map on empty array which won't fill correctly; const dp = new Array(n).fill(null); fills with nulls; const dp = Array.fill(n+1, 0); is invalid syntax.

3. Final Answer:

   const dp = new Array(n+1).fill(0); -> Option A

4. Quick Check:

   Array fill with zeros = new Array(n+1).fill(0) [OK]

Hint: Use new Array(size).fill(value) to initialize arrays [OK]

Common Mistakes:

• Using map on empty array without elements
• Wrong array size (n instead of n+1)
• Using invalid Array.fill syntax

3. What will be the output of the following TypeScript code using bottom-up DP to find the nth Fibonacci number?

function fib(n: number): number {
  const dp = new Array(n + 1).fill(0);
  dp[1] = 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. 5

C. 8

D. 13

Solution

1. Step 1: Trace dp array filling for n=5

   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 B

4. Quick Check:

   Fibonacci(5) = 5 [OK]

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

Common Mistakes:

• Starting dp[1] as 0 instead of 1
• Off-by-one errors in loop
• Returning dp[n-1] instead of dp[n]

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

function factorial(n: number): number {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] * i;
  }
  return dp[n];
}
console.log(factorial(4));

medium

A. The loop should start from i = 0

B. dp array should be initialized with zeros, not ones

C. The multiplication should be dp[i] = dp[i] * i

D. dp[0] should be set to 1 before the loop

Solution

1. Step 1: Check dp initialization and base case

   dp is filled with 0s, but dp[0] must be explicitly set to 1 as factorial(0)=1.

2. Step 2: Verify loop correctness

   Loop from i=1 to n is correct; dp[i] = dp[i-1] * i is correct formula.

3. Final Answer:

   dp[0] should be set to 1 before the loop -> Option D

4. Quick Check:

   Base case dp[0]=1 needed [OK]

Hint: Always set base case explicitly in DP arrays [OK]

Common Mistakes:

• Starting loop at 0 causing dp[-1] access
• Wrong initialization of dp array
• Incorrect multiplication formula

5. You want to find the minimum number of coins needed to make amount n using coins of denominations [1, 3, 4] with bottom-up DP. Which of these is the correct tabulation approach?

hard

A. Initialize dp array with zeros; for each coin, add 1 to dp[coin] only once

B. Use recursion to try all coin combinations without dp array

C. Initialize dp array with Infinity except dp[0]=0; for each amount i from 1 to n, update dp[i] = min(dp[i], dp[i - coin] + 1) for each coin if i >= coin

D. Initialize dp array with zeros; for each amount i, set dp[i] = dp[i-1] + 1 only

Solution

1. Step 1: Understand coin change tabulation

   We start dp with Infinity except dp[0]=0 because 0 coins needed for amount 0.

2. Step 2: Update dp for each amount and coin

   For each amount i, check all coins; if coin <= i, update dp[i] = min(dp[i], dp[i-coin] + 1).

3. Final Answer:

   Initialize dp array with Infinity except dp[0]=0; for each amount i from 1 to n, update dp[i] = min(dp[i], dp[i - coin] + 1) for each coin if i >= coin -> Option C

4. Quick Check:

   Coin change DP = min coins with dp and Infinity init [OK]

Hint: Use Infinity init and min update for coin change DP [OK]

Common Mistakes:

• Not initializing dp with Infinity
• Ignoring multiple coin options per amount
• Using recursion instead of tabulation