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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci Tabulation

What is the output of this code that uses bottom-up DP to find the 6th Fibonacci number?

DSA Python

def fib_tab(n):
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_tab(6))

A 13

B 5

C 8

D 21

💡 Hint

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

The 6th Fibonacci number (0-based index) is 8 using bottom-up DP.

❓ Predict Output

intermediate

Number of ways to climb stairs

What is the output of this code that counts ways to climb 4 stairs taking 1 or 2 steps at a time?

DSA Python

def climb_stairs(n):
    dp = [0] * (n+1)
    dp[0] = 1
    for i in range(1, n+1):
        dp[i] = dp[i-1]
        if i > 1:
            dp[i] += dp[i-2]
    return dp[n]

print(climb_stairs(4))

A 5

B 6

C 7

D 4

💡 Hint

Think of ways to reach step i from i-1 and i-2.

The ways to climb 4 stairs are 5 using bottom-up DP.

❓ Predict Output

advanced

Longest Common Subsequence length

What is the output of this code that finds the length of the longest common subsequence of 'abcde' and 'ace' using bottom-up DP?

DSA Python

def lcs_length(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs_length('abcde', 'ace'))

A 3

B 2

C 4

D 5

💡 Hint

Longest common subsequence of 'abcde' and 'ace' is 'ace'.

The LCS length is 3 for 'ace'.

🔧 Debug

advanced

Identify error in coin change tabulation

What error does this code produce when trying to find number of ways to make amount 5 with coins [1,2,3] using bottom-up DP?

DSA Python

def coin_change(coins, amount):
    dp = [0] * (amount+1)
    dp[0] = 1
    for coin in coins:
        for x in range(coin, amount+1):
            dp[x] += dp[x-coin]
    return dp[amount]

print(coin_change([1,2,3], 5))

A IndexError: list index out of range

B No error, output is 5

C TypeError: unsupported operand type(s)

D Output is 6

💡 Hint

Count ways to make 5 with coins 1,2,3 carefully.

There is no error; the code correctly computes 5 ways using bottom-up DP.

🧠 Conceptual

expert

Minimum edit distance tabulation result

Given strings 'kitten' and 'sitting', what is the minimum edit distance computed by this bottom-up DP code?

DSA Python

def min_edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

print(min_edit_distance('kitten', 'sitting'))

A 6

B 5

C 4

D 3

💡 Hint

Edit distance counts insertions, deletions, substitutions.

Minimum edit distance between 'kitten' and 'sitting' is 3.

Practice

1. What is the main idea behind Tabulation Bottom Up DP in dynamic programming?

easy

A. Start solving from the largest problem and break it down

B. Solve the problem by recursion without storing results

C. Use random guesses to find the solution

D. Build a table from the smallest subproblems up to the main problem

Solution

1. Step 1: Understand bottom-up approach

   Tabulation means filling a table starting from the smallest subproblems, so we solve all smaller parts first.

2. Step 2: Compare with other methods

   Unlike recursion without storage, tabulation avoids repeated work by storing results in a table.

3. Final Answer:

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

4. Quick Check:

   Tabulation = Bottom-up table filling [OK]

Hint: Think: solve small parts first, then bigger ones [OK]

Common Mistakes:

• Confusing tabulation with recursion
• Thinking tabulation starts from the biggest problem
• Ignoring the use of a table to store results

2. Which of the following is the correct way to initialize a DP table for the Fibonacci sequence using tabulation in Python?

easy

A. dp = [0, 1] + [0] * (n - 2)

B. dp = [1, 1] * n

C. dp = [0] * n; dp[0] = 1; dp[1] = 1

D. dp = [0] * (n + 1); dp[0] = 1

Solution

1. Step 1: Understand Fibonacci base cases

   Fibonacci starts with dp[0] = 0 and dp[1] = 1, so initialization must reflect that.

2. Step 2: Check each option

   dp = [0, 1] + [0] * (n - 2) correctly sets dp[0]=0, dp[1]=1, and fills the rest with zeros for further calculation.

3. Final Answer:

   dp = [0, 1] + [0] * (n - 2) -> Option A

4. Quick Check:

   Correct base cases = dp = [0, 1] + [0] * (n - 2) [OK]

Hint: Start dp with base Fibonacci values 0 and 1 [OK]

Common Mistakes:

• Setting wrong base values
• Using multiplication incorrectly for initialization
• Not allocating enough space for dp

3. What will be the output of the following code snippet?

def fib(n):
    dp = [0, 1] + [0] * (n - 2)
    for i in range(2, n):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n-1]

print(fib(6))

medium

A. 5

B. 8

C. 13

D. 3

Solution

1. Step 1: Trace the DP table filling

   dp starts as [0,1,0,0,0,0]. Iterations fill dp as: dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5.

2. Step 2: Return the last element dp[5]

   dp[5] = 5, so fib(6) returns 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Fibonacci(6) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Off-by-one errors in indexing
• Confusing dp[n-1] with dp[n]
• Incorrect loop range

4. Find the error in the following tabulation code for Fibonacci and select the fix:

def fib(n):
    dp = [0] * n
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib(5))

medium

A. Start loop from i=1 instead of i=2

B. Initialize dp with size n+1

C. Change return dp[n] to return dp[n-1]

D. Set dp[0] = 1 and dp[1] = 1

Solution

1. Step 1: Identify index error in return statement

   dp has indices 0 to n-1, so dp[n] is out of range causing error.

2. Step 2: Fix by returning dp[n-1]

   Returning dp[n-1] gives the last Fibonacci number correctly.

3. Final Answer:

   Change return dp[n] to return dp[n-1] -> Option C

4. Quick Check:

   Index error fixed by dp[n-1] return [OK]

Hint: Return dp[n-1] for nth Fibonacci (0-based index) [OK]

Common Mistakes:

• Returning dp[n] causing index error
• Wrong loop start index
• Incorrect base values

5. Given a list of coin denominations coins = [1, 2, 5] and an amount amount = 5, which tabulation code correctly computes the number of ways to make the amount using these coins?

hard

A. dp = [0]*(amount+1)
dp[0] = 1
for x in range(1, amount+1):
for coin in coins:
if coin <= x:
dp[x] += dp[x-coin]
print(dp[amount])

B. dp = [1] + [0]*amount
for coin in coins:
for x in range(coin, amount+1):
dp[x] += dp[x-coin]
print(dp[amount])

C. dp = [0]*(amount+1)
dp[0] = 1
for coin in coins:
for x in range(amount, coin-1, -1):
dp[x] += dp[x-coin]
print(dp[amount])

D. dp = [0]*(amount+1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount+1):
dp[x] = dp[x-coin]
print(dp[amount])

Solution

1. Step 1: Understand coin change tabulation

   We initialize dp[0] = 1 (one way to make zero). For each coin, update dp[x] by adding dp[x-coin].

2. Step 2: Check each option's correctness

   dp = [1] + [0]*amount for coin in coins: for x in range(coin, amount+1): dp[x] += dp[x-coin] print(dp[amount]) correctly uses nested loops with dp[x] += dp[x-coin]. dp = [0]*(amount+1) dp[0] = 1 for x in range(1, amount+1): for coin in coins: if coin <= x: dp[x] += dp[x-coin] print(dp[amount]) loops coins inside amount, which counts duplicates. dp = [0]*(amount+1) dp[0] = 1 for coin in coins: for x in range(amount+1): if x >= coin: dp[x] += dp[x-coin] print(dp[amount]) loops x from 0 causing extra checks. dp = [0]*(amount+1) dp[0] = 1 for coin in coins: for x in range(coin, amount+1): dp[x] = dp[x-coin] print(dp[amount]) overwrites dp[x] instead of adding.

3. Final Answer:

   dp = [1] + [0]*amount for coin in coins: for x in range(coin, amount+1): dp[x] += dp[x-coin] print(dp[amount]) -> Option B

4. Quick Check:

   Correct coin change tabulation = dp = [1] + [0]*amount for coin in coins: for x in range(coin, amount+1): dp[x] += dp[x-coin] print(dp[amount]) [OK]

Hint: Add ways, don't overwrite dp[x] when counting combinations [OK]

Common Mistakes:

• Overwriting dp[x] instead of adding
• Wrong loop order causing duplicates
• Not initializing dp[0] = 1