Tabulation Bottom Up DP in DSA Go - Build from Scratch

Tabulation Bottom Up DP: Climbing Stairs Problem

📖 Scenario: Imagine you want to climb a staircase with 5 steps. You can take either 1 step or 2 steps at a time. You want to find out how many different ways you can reach the top.

🎯 Goal: Build a Go program that uses tabulation (bottom-up dynamic programming) to calculate the number of ways to climb a staircase of 5 steps, taking 1 or 2 steps at a time.

📋 What You'll Learn

Create a slice called dp with length 6 to store ways to reach each step (0 to 5).

Initialize dp[0] to 1 as the base case.

Use a for loop with variable i from 1 to 5 to fill dp using previous values.

Print the value of dp[5] which is the total ways to reach step 5.

💡 Why This Matters

🌍 Real World

This problem models real-life situations where you want to count possible ways to reach a goal by taking small steps, like climbing stairs or moving through stages.

💼 Career

Understanding bottom-up dynamic programming is essential for solving optimization problems efficiently in software engineering and technical interviews.

1

Create the DP slice

Create a slice called dp of type int with length 6 to store the number of ways to reach each step.

DSA Go

package main

func main() {
    // Create a slice called dp with length 6
    // Your code here
}

Hint

Use make([]int, 6) to create a slice of integers with length 6.

2

Initialize base case

Set dp[0] to 1 because there is exactly one way to stand at the bottom without climbing any steps.

DSA Go

package main

func main() {
    dp := make([]int, 6)
    // Initialize dp[0] to 1
    // Your code here
}

Hint

Set the first element of dp to 1 to represent the base case.

3

Fill dp slice using bottom-up approach

Use a for loop with variable i from 1 to 5. For each i, add dp[i-1] to dp[i]. If i is greater than or equal to 2, also add dp[i-2] to dp[i].

DSA Go

package main

func main() {
    dp := make([]int, 6)
    dp[0] = 1
    // Use a for loop from i = 1 to 5
    // Update dp[i] using dp[i-1] and dp[i-2]
    // Your code here
}

Hint

Remember to check if i is at least 2 before accessing dp[i-2] to avoid errors.

4

Print the total ways to climb 5 steps

Use fmt.Println(dp[5]) to print the total number of ways to reach step 5.

DSA Go

package main

import "fmt"

func main() {
    dp := make([]int, 6)
    dp[0] = 1
    for i := 1; i = 2 {
            dp[i] += dp[i-2]
        }
    }
    // Print the number of ways to climb 5 steps
    // Your code here
}

Hint

Use fmt.Println(dp[5]) to show the final 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]