Tabulation Bottom Up DP in DSA Go - 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 with a table of zeros. Fill it row by row using previous results. The last cell holds the answer.

Execution Sample

DSA Go

weights := []int{1, 3, 4}
values := []int{1, 4, 5}
W := 7
// Initialize dp table
 dp := make([][]int, len(weights)+1)
 for i := range dp {
   dp[i] = make([]int, W+1)
 }
// dp[i][w] = max value using first i items with capacity w
for i := 1; i <= len(weights); i++ {
  for w := 1; w <= W; w++ {
    if weights[i-1] <= w {
      dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
    } else {
      dp[i][w] = dp[i-1][w]
    }
  }
}

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

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

Execution Table

Step	Operation	Item Index (i)	Capacity (w)	DP Cell Computed	Value Computed	DP Table Row State
1	Initialize base row	0	0 to 7	dp[0][w]	0	[0, 0, 0, 0, 0, 0, 0, 0]
2	Compute dp[1][1]	1	1	dp[1][1]	1	[0, 1, 0, 0, 0, 0, 0, 0]
3	Compute dp[1][2]	1	2	dp[1][2]	1	[0, 1, 1, 0, 0, 0, 0, 0]
4	Compute dp[1][3]	1	3	dp[1][3]	1	[0, 1, 1, 1, 0, 0, 0, 0]
5	Compute dp[1][4]	1	4	dp[1][4]	1	[0, 1, 1, 1, 1, 0, 0, 0]
6	Compute dp[1][5]	1	5	dp[1][5]	1	[0, 1, 1, 1, 1, 1, 0, 0]
7	Compute dp[1][6]	1	6	dp[1][6]	1	[0, 1, 1, 1, 1, 1, 1, 0]
8	Compute dp[1][7]	1	7	dp[1][7]	1	[0, 1, 1, 1, 1, 1, 1, 1]
9	Compute dp[2][1]	2	1	dp[2][1]	1	[0, 1, 1, 0, 0, 0, 0, 0]
10	Compute dp[2][2]	2	2	dp[2][2]	1	[0, 1, 1, 0, 0, 0, 0, 0]
11	Compute dp[2][3]	2	3	dp[2][3]	4	[0, 1, 1, 4, 0, 0, 0, 0]
12	Compute dp[2][4]	2	4	dp[2][4]	5	[0, 1, 1, 4, 5, 0, 0, 0]
13	Compute dp[2][5]	2	5	dp[2][5]	5	[0, 1, 1, 4, 5, 5, 0, 0]
14	Compute dp[2][6]	2	6	dp[2][6]	5	[0, 1, 1, 4, 5, 5, 5, 0]
15	Compute dp[2][7]	2	7	dp[2][7]	5	[0, 1, 1, 4, 5, 5, 5, 5]
16	Compute dp[3][1]	3	1	dp[3][1]	1	[0, 1, 1, 4, 5, 0, 0, 0]
17	Compute dp[3][2]	3	2	dp[3][2]	1	[0, 1, 1, 4, 5, 0, 0, 0]
18	Compute dp[3][3]	3	3	dp[3][3]	4	[0, 1, 1, 4, 5, 0, 0, 0]
19	Compute dp[3][4]	3	4	dp[3][4]	5	[0, 1, 1, 4, 5, 0, 0, 0]
20	Compute dp[3][5]	3	5	dp[3][5]	6	[0, 1, 1, 4, 5, 6, 0, 0]
21	Compute dp[3][6]	3	6	dp[3][6]	6	[0, 1, 1, 4, 5, 6, 6, 0]
22	Compute dp[3][7]	3	7	dp[3][7]	9	[0, 1, 1, 4, 5, 6, 6, 9]
23	End	-	-	-	-	Final answer dp[3][7] = 9

💡 All items and capacities processed; final answer found at dp[last item][max capacity]

Variable Tracker

Variable	Start	After Step 8	After Step 15	After Step 22	Final
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,0,0,0,0,0,0,0]
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 dp[1][1] and not dp[0][0]?

dp[0][w] row represents using zero items, so values are zero. We start filling from dp[1][1] because it represents using the first item and capacity 1. See execution_table rows 2-8.

Why do we compare dp[i-1][w] and values[i-1] + dp[i-1][w-weights[i-1]]?

We decide whether to include the current item or not. dp[i-1][w] is value without current item; values[i-1] + dp[i-1][w-weights[i-1]] is value including it. The max is chosen. See execution_table rows 11-22.

Why does the capacity loop go from 1 to W and not the other way?

We fill the table left to right to ensure smaller capacities are computed before larger ones, so dp[i-1][w-weights[i-1]] is ready when needed. See code in execution_sample and execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 15. What is the value computed for dp[2][7]?

A 5

B 6

C 9

D 10

💡 Hint

Check the 'Value Computed' column at step 15 in execution_table.

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

A Step 12

B Step 20

C Step 15

D Step 22

💡 Hint

Look at the 'Value Computed' column and DP Table Row State in execution_table rows 12-22.

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

A It would become 1

B It would remain 4

C It would become 5

D It would become 0

💡 Hint

If weight decreases, more capacity is available to include the item, increasing dp value. See execution_table step 11 logic.

Concept Snapshot

Tabulation Bottom Up DP:
- Build a 2D table dp[item][capacity]
- dp[i][w] = max value using first i items with capacity w
- Fill table row by row from base case dp[0][w] = 0
- Use previous row values to compute current
- Final answer at dp[last item][max capacity]

Full Transcript

Tabulation Bottom Up DP builds a table to solve problems like 0/1 Knapsack. We start with a base row of zeros representing no items. Then for each item and capacity, we decide to include or exclude the item by comparing values from the previous row. We fill the table row by row until the last cell contains the maximum value achievable. This method avoids recursion by iteratively building solutions to subproblems.

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. Build a table from the smallest subproblems up to the main problem

D. Start solving from the largest problem and go downwards

Solution

1. Step 1: Understand tabulation approach

   Tabulation means filling a table starting from the smallest subproblems.

2. Step 2: Compare with other methods

   Unlike recursion, tabulation solves subproblems first and uses their answers to solve bigger problems.

3. Final Answer:

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

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 starts from the largest problem
• Ignoring the use of a table to store results

2. Which of the following Go code snippets correctly initializes a DP table for tabulation with size n+1 and zero values?

easy

A. dp := []int{n+1}

B. dp := make([]int, n)

C. dp := new(int, n+1)

D. dp := make([]int, n+1)

Solution

1. Step 1: Understand Go slice initialization

   To create a slice of integers with length n+1 filled with zeros, use make([]int, n+1).

2. Step 2: Check other options

   dp := make([]int, n) creates size n, not n+1; dp := []int{n+1} is invalid syntax; dp := new(int, n+1) is invalid for slices.

3. Final Answer:

   dp := make([]int, n+1) -> Option D

4. Quick Check:

   make([]int, n+1) creates zero-filled slice [OK]

Hint: Use make([]int, size) for zero-filled slices [OK]

Common Mistakes:

• Using wrong slice size (n instead of n+1)
• Using new() which returns pointer, not slice
• Incorrect slice literal syntax

3. What is the output of the following Go code using bottom-up DP to compute Fibonacci numbers?

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

fmt.Println(fib(5))

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Trace DP table 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 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 loop
• Wrong base cases initialization
• Confusing dp indices

4. Identify the bug in this bottom-up DP code for computing factorial in Go:

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

medium

A. dp slice size should be n, not n+1

B. Loop should run until i <= n, not i < n

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

D. dp[0] should be 0, not 1

Solution

1. Step 1: Check loop range for factorial calculation

   Factorial needs to compute dp[n], so loop must include i = n (i <= n).

2. Step 2: Identify impact of loop range

   Current loop stops at i = n-1, so dp[n] remains zero, causing wrong return.

3. Final Answer:

   Loop should run until i <= n, not i < n -> Option B

4. Quick Check:

   Loop must cover all factorial steps [OK]

Hint: Factorial needs full range including n [OK]

Common Mistakes:

• Stopping loop before n
• Wrong base case initialization
• Returning wrong dp index

5. Given a list of coin denominations coins := []int{1, 2, 5} and an amount amount := 5, which bottom-up DP code snippet correctly computes the minimum number of coins needed to make the amount? Assume impossible cases return -1.

hard

A. dp := make([]int, amount+1); for i := range dp { dp[i] = amount+1 }; dp[0] = 0; for i := 1; i <= amount; i++ { for _, c := range coins { if c <= i && dp[i-c]+1 < dp[i] { dp[i] = dp[i-c] + 1 } } }; if dp[amount] > amount { return -1 } else { return dp[amount] }

B. dp := make([]int, amount); dp[0] = 0; for i := 1; i < amount; i++ { for _, c := range coins { if c <= i { dp[i] = dp[i-c] + 1 } } }; return dp[amount]

C. dp := make([]int, amount+1); dp[0] = 1; for i := 1; i <= amount; i++ { for _, c := range coins { if c <= i { dp[i] = dp[i-c] + 1 } } }; return dp[amount]

D. dp := make([]int, amount+1); for i := 0; i <= amount; i++ { dp[i] = 0 }; for i := 1; i <= amount; i++ { for _, c := range coins { if c <= i && dp[i-c] != 0 { dp[i] = dp[i-c] + 1 } } }; return dp[amount]

Solution

1. Step 1: Initialize dp with large values and base case

   Set dp size to amount+1, fill with amount+1 (impossible large), and dp[0]=0.

2. Step 2: Update dp with minimum coins for each amount

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

3. Step 3: Return result or -1 if impossible

   If dp[amount] > amount, return -1; else return dp[amount].

4. Final Answer:

   Option A code snippet -> Option A

5. Quick Check:

   Proper initialization and min update needed [OK]

Hint: Initialize dp with large number, update min coins [OK]

Common Mistakes:

• Wrong dp size or initialization
• Not checking if dp[i-c] is valid
• Incorrect base case dp[0]