Tabulation Bottom Up DP in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom-Up DP Fibonacci Implementation

What is the output of this Go code that uses bottom-up dynamic programming to find the 7th Fibonacci number?

DSA Go

package main
import "fmt"
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]
}
func main() {
    fmt.Println(fib(7))
}

A 13

B 21

C 8

D 34

💡 Hint

Remember Fibonacci sequence starts 0,1,1,2,3,5,8,13,...

The 7th Fibonacci number (0-based index) is 13. The code builds the sequence bottom-up and returns dp[7].

🧠 Conceptual

intermediate

Understanding Table Initialization in Bottom-Up DP

In bottom-up dynamic programming, why do we initialize the dp table with base cases before the loop?

A To provide starting values so subsequent states can be computed correctly

B To save memory by avoiding unnecessary allocations

C To speed up the program by skipping the loop entirely

D To ensure the dp table is sorted before processing

💡 Hint

Think about how each dp state depends on previous states.

Base cases give known answers that the loop uses to build solutions for bigger problems.

❓ Predict Output

advanced

Output of Bottom-Up DP for Coin Change Ways

What is the output of this Go code that calculates the number of ways to make amount 5 using coins [1,2,5] with bottom-up DP?

DSA Go

package main
import "fmt"
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for _, coin := range coins {
        for x := coin; x <= amount; x++ {
            dp[x] += dp[x-coin]
        }
    }
    return dp[amount]
}
func main() {
    fmt.Println(change(5, []int{1, 2, 5}))
}

A 3

B 4

C 5

D 2

💡 Hint

Count combinations: {1+1+1+1+1}, {1+1+1+2}, {1+2+2}, {5}

The code counts 4 ways to make 5: using coins 1,2,5 in combinations.

🔧 Debug

advanced

Identify the Error in Bottom-Up DP for Longest Increasing Subsequence

What error will this Go code produce when computing the length of the longest increasing subsequence using bottom-up DP?

DSA Go

package main
import "fmt"
func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    maxLen := 1
    for i := 0; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        if dp[i] > maxLen {
            maxLen = dp[i]
        }
    }
    return maxLen
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func main() {
    fmt.Println(lengthOfLIS([]int{10,9,2,5,3,7,101,18}))
}

A Output is 0 instead of expected value

B Runtime panic: index out of range

C Compilation error: undefined function max

D No error, output is 4

💡 Hint

Check if all functions are defined and used correctly.

The code correctly implements bottom-up DP for LIS and prints 4.

🚀 Application

expert

Minimum Steps to One Using Bottom-Up DP

Given the code below, what is the value of dp[10] after running the bottom-up DP to find minimum steps to reduce 10 to 1 by subtracting 1, dividing by 2, or dividing by 3?

DSA Go

package main
import "fmt"
func minSteps(n int) int {
    dp := make([]int, n+1)
    dp[1] = 0
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + 1
        if i%2 == 0 && dp[i/2]+1 < dp[i] {
            dp[i] = dp[i/2] + 1
        }
        if i%3 == 0 && dp[i/3]+1 < dp[i] {
            dp[i] = dp[i/3] + 1
        }
    }
    return dp[n]
}
func main() {
    fmt.Println(minSteps(10))
}

A 4

B 5

C 3

D 2

💡 Hint

Trace steps: 10->9->3->1 (3 steps)

The minimum steps to reduce 10 to 1 are 3 using the allowed operations.

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]