Tabulation Bottom Up DP in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP table with zeros.

DSA Go

dp := make([]int, [1])

Drag options to blanks, or click blank then click option'

An/2

Bn*2

Cn+1

Dn-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of n+1 causes index out of range errors.

Using n-1 misses the last element in the DP table.

We create a DP table of size n+1 to include the base case at index 0.

2fill in blank

medium

Complete the code to fill the DP table bottom-up for the Fibonacci sequence.

DSA Go

for i := 2; i <= n; i++ {
    dp[i] = dp[i-1] [1] dp[i-2]
}

Drag options to blanks, or click blank then click option'

A+

B*

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication or subtraction instead of addition.

Using division which is not part of Fibonacci calculation.

Fibonacci numbers are the sum of the two previous numbers.

3fill in blank

hard

Fix the error in the loop condition to avoid index out of range.

DSA Go

for i := 2; i < [1]; i++ {
    dp[i] = dp[i-1] + dp[i-2]
}

Drag options to blanks, or click blank then click option'

An+1

Bn-1

Cn

Dlen(dp)

Attempts:

3 left

💡 Hint

Common Mistakes

Using n causes the last dp element to be skipped.

Using n-1 causes incomplete computation.

The loop must run until i equals n inclusive, so use n+1.

4fill in blank

hard

Fill both blanks to create a DP table for the coin change problem counting ways.

DSA Go

dp := make([]int, [1])
dp[0] = [2]

Drag options to blanks, or click blank then click option'

Aamount+1

B0

C1

Damount

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[0] to 0 causes incorrect counting.

Using amount instead of amount+1 causes index errors.

The DP table size is amount+1 to include zero amount, and dp[0] = 1 as base case.

5fill in blank

hard

Fill all three blanks to complete the nested loops for the coin change problem.

DSA Go

for _, coin := range coins {
    for x := [1]; x <= [2]; x++ {
        if x >= coin {
            dp[x] += dp[x-[3]]
        }
    }
}

Drag options to blanks, or click blank then click option'

Acoin

Bamount

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Starting inner loop at 0 leads to unnecessary iterations.

Using wrong index in dp[x-...] causes incorrect results.

The inner loop starts from coin value to amount, and dp[x] adds dp[x-coin].

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]