Tabulation Bottom Up DP in DSA Go

Mental Model

Start solving the smallest parts first and build up to the full problem step by step.

Analogy: Like stacking blocks from the bottom to the top, each block depends on the ones below it.

Index: 0  1  2  3  4  5
DP:   [0][ ][ ][ ][ ][ ]
          ↑

Dry Run Walkthrough

Input: Find the 5th Fibonacci number using bottom-up tabulation

Goal: Calculate Fibonacci numbers from 0 to 5 step by step and get the 5th number

Step 1: Initialize base cases: fib[0] = 0, fib[1] = 1

fib: [0][1][ ][ ][ ][ ]

Why: Base cases are known and needed to build next values

Step 2: Calculate fib[2] = fib[1] + fib[0] = 1 + 0 = 1

fib: [0][1][1][ ][ ][ ]

Why: Use previous two results to find current value

Step 3: Calculate fib[3] = fib[2] + fib[1] = 1 + 1 = 2

fib: [0][1][1][2][ ][ ]

Why: Build on already computed values

Step 4: Calculate fib[4] = fib[3] + fib[2] = 2 + 1 = 3

fib: [0][1][1][2][3][ ]

Why: Continue building up from smaller subproblems

Step 5: Calculate fib[5] = fib[4] + fib[3] = 3 + 2 = 5

fib: [0][1][1][2][3][5]

Why: Final value is computed from previous two

Result:

fib: [0][1][1][2][3][5]
Answer: 5

Annotated Code

DSA Go

package main

import "fmt"

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

func main() {
    n := 5
    result := fibonacci(n)
    fmt.Printf("fib: %v\n", fibArray(n))
    fmt.Printf("Answer: %d\n", result)
}

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

fib[0], fib[1] = 0, 1

Initialize base cases for Fibonacci

for i := 2; i <= n; i++ {

Iterate from 2 to n to fill DP table

fib[i] = fib[i-1] + fib[i-2]

Calculate current Fibonacci using previous two

return fib[n]

Return the final computed Fibonacci number

Output

fib: [0 1 1 2 3 5]

Answer: 5

Complexity Analysis

Time: O(n) because we fill the table once from 0 to n

Space: O(n) because we store all Fibonacci numbers up to n

vs Alternative: Compared to naive recursion which is exponential, tabulation is much faster and avoids repeated work

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Go

if n <= 1 { return n }

n = 1

Returns 1 immediately as base case

DSA Go

if n <= 1 { return n }

When to Use This Pattern

When you see a problem that can be broken into smaller overlapping subproblems and you want to avoid repeated work, use bottom-up tabulation to build solutions from smallest to largest.

Common Mistakes

Mistake: Not initializing base cases before filling the table
Fix: Always set the known starting values before the loop

Mistake: Starting loop from 0 or 1 instead of 2
Fix: Start from 2 because 0 and 1 are base cases already set

Summary

Calculates results by filling a table from smallest subproblems up to the full problem.

Use when you can solve a problem by combining solutions to smaller parts without recursion overhead.

The key is to solve and store all smaller problems first, then build up to the answer.

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]