Tabulation Bottom Up DP in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom-Up DP Fibonacci Calculation

What is the output of this C# code that calculates Fibonacci numbers using bottom-up tabulation?

DSA C#

int n = 6;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
    dp[i] = dp[i - 1] + dp[i - 2];
}
Console.WriteLine(string.Join(", ", dp));

A [0, 1, 1, 3, 4, 7, 11]

B [0, 1, 2, 3, 5, 8, 13]

C [1, 1, 2, 3, 5, 8, 13]

D [0, 1, 1, 2, 3, 5, 8]

💡 Hint

Remember Fibonacci starts with 0 and 1, and each next number is sum of previous two.

The code initializes dp[0] = 0 and dp[1] = 1. Then each dp[i] is dp[i-1] + dp[i-2]. So dp array becomes [0,1,1,2,3,5,8].

❓ Predict Output

intermediate

Output of Bottom-Up DP for Coin Change Ways

What is the output of this C# code that calculates the number of ways to make amount 5 using coins {1, 2} with bottom-up DP?

DSA C#

int amount = 5;
int[] coins = {1, 2};
int[] dp = new int[amount + 1];
dp[0] = 1;
foreach (int coin in coins)
{
    for (int i = coin; i <= amount; i++)
    {
        dp[i] += dp[i - coin];
    }
}
Console.WriteLine(dp[amount]);

A 3

B 5

C 4

D 6

💡 Hint

Think about combinations of 1s and 2s that sum to 5.

The ways to make 5 are: five 1s, three 1s + one 2, one 1 + two 2s. Total 3 ways.

🧠 Conceptual

advanced

Understanding DP Table Construction Order

In bottom-up DP, why do we fill the table starting from the smallest subproblems to the largest?

A Because it reduces the memory usage drastically.

B Because larger subproblems are easier to solve first.

C Because smaller subproblems provide solutions needed to solve larger subproblems.

D Because it avoids the need for recursion entirely.

💡 Hint

Think about dependencies between subproblems.

Bottom-up DP solves smaller subproblems first because their results are needed to solve bigger subproblems. This order ensures all needed values are ready.

🔧 Debug

advanced

Identify the Bug in Bottom-Up DP for Climbing Stairs

What error does this C# code produce when calculating ways to climb 4 stairs taking 1 or 2 steps at a time?

DSA C#

int n = 4;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
    dp[i] = dp[i - 1] + dp[i - 3];
}
Console.WriteLine(dp[n]);

A IndexOutOfRangeException

B Output: 5

C Output: 7

D Output: 3

💡 Hint

Check the index used inside the loop for dp array access.

At i=2, dp[i-3] is dp[-1], which is invalid index causing IndexOutOfRangeException.

🚀 Application

expert

Final DP Table for Longest Increasing Subsequence Length

Given the array [10, 9, 2, 5, 3, 7, 101, 18], what is the final dp table (lengths of LIS ending at each index) after bottom-up DP computation?

DSA C#

int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
int n = nums.Length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) dp[i] = 1;
for (int i = 1; i < n; i++)
{
    for (int j = 0; j < i; j++)
    {
        if (nums[i] > nums[j])
        {
            dp[i] = Math.Max(dp[i], dp[j] + 1);
        }
    }
}
Console.WriteLine(string.Join(", ", dp));

A [1, 2, 1, 3, 2, 4, 5, 6]

B [1, 1, 1, 2, 2, 3, 4, 4]

C [1, 1, 2, 2, 3, 3, 4, 5]

D [1, 1, 1, 1, 1, 1, 1, 1]

💡 Hint

Each dp[i] stores length of longest increasing subsequence ending at i.

The dp array after computation is [1,1,1,2,2,3,4,4]. For example, at index 5 (value 7), LIS length is 3 (2,3,7).

Practice

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

easy

A. Start solving from the main problem and break it down recursively

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, building up to the final answer.

2. Step 2: Compare with other methods

   Unlike recursion without memoization, 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 [OK]

Common Mistakes:

• Confusing tabulation with recursion
• Ignoring the order of filling the table
• Not storing intermediate results

2. Which of the following is the correct way to initialize a tabulation array for Fibonacci numbers in C#?

easy

A. int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 0;

B. int[] dp = new int[n]; dp[0] = 1; dp[1] = 1;

C. int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1;

D. int[] dp = new int[n]; dp[0] = 0; dp[1] = 1;

Solution

1. Step 1: Check array size and base cases

   For Fibonacci, dp array size should be n+1 to include dp[n]. Base cases are dp[0]=0 and dp[1]=1.

2. Step 2: Verify initialization correctness

   int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; correctly initializes dp with size n+1 and sets dp[0]=0, dp[1]=1.

3. Final Answer:

   int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; -> Option C

4. Quick Check:

   Correct array size and base values [OK]

Hint: Remember Fibonacci base: 0 and 1 at dp[0], dp[1] [OK]

Common Mistakes:

• Using wrong array size (n instead of n+1)
• Swapping base values dp[0] and dp[1]
• Not initializing base cases

3. What will be the output of the following C# code using bottom-up DP to find the number of ways to climb 3 steps if you can take 1 or 2 steps at a time?

int n = 3;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
Console.WriteLine(dp[n]);

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Understand dp array meaning

   dp[i] stores number of ways to reach step i. Base: dp[0]=1 (one way to stand still), dp[1]=1 (one way to step 1).

2. Step 2: Calculate dp values up to n=3

   dp[2] = dp[1] + dp[0] = 1 + 1 = 2; dp[3] = dp[2] + dp[1] = 2 + 1 = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Ways to climb 3 steps = 3 [OK]

Hint: Sum ways to previous two steps for each step [OK]

Common Mistakes:

• Confusing dp indices or base cases
• Off-by-one errors in loop
• Misunderstanding dp meaning

4. Identify the error in this bottom-up DP code snippet for calculating factorial of n:

int n = 5;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] * i;
}
Console.WriteLine(dp[n]);

medium

A. No error, code works correctly

B. Array dp should be of size n, not n+1

C. dp[0] should be initialized to 0

D. Loop should start from i = 0

Solution

1. Step 1: Check array size and initialization

   dp size n+1 is correct to store factorials from 0 to n. dp[0] = 1 is correct as 0! = 1.

2. Step 2: Verify loop and calculation

   Loop from i=1 to n correctly calculates dp[i] = dp[i-1] * i, which is factorial definition.

3. Final Answer:

   No error, code works correctly -> Option A

4. Quick Check:

   Factorial DP code is correct [OK]

Hint: Check base case and loop range carefully [OK]

Common Mistakes:

• Wrong dp array size causing index errors
• Incorrect base case initialization
• Starting loop at wrong index

5. Given a list of coin denominations coins = {1, 2, 5} and a target amount amount = 5, which bottom-up DP approach correctly computes the minimum number of coins needed to make the amount?

int amount = 5;
int[] dp = new int[amount + 1];
for (int i = 1; i <= amount; i++) dp[i] = int.MaxValue;
int[] coins = {1, 2, 5};
for (int i = 1; i <= amount; i++) {
    foreach (int coin in coins) {
        if (coin <= i && dp[i - coin] != int.MaxValue) {
            dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
        }
    }
}
Console.WriteLine(dp[amount]);

hard

A. 1

B. 2

C. 3

D. 5

Solution

1. Step 1: Understand dp meaning and initialization

   dp[i] stores minimum coins to make amount i. Initialized dp[0]=0 (default), others to MaxValue.

2. Step 2: Calculate dp values for amount=5

   Calculate dp[1]=1 (coin 1), dp[2]=1 (coin 2), dp[3]=2 (1+2), dp[4]=2 (2+2), dp[5]=1 (coin 5). Minimum coins for 5 is 1.

3. Step 3: Re-check code logic

   Code correctly updates dp[i] with minimum coins. Output dp[5] = 1.

4. Final Answer:

   1 -> Option A

5. Quick Check:

   Minimum coins for 5 = 1 (coin 5) [OK]

Hint: Check dp updates with all coins for each amount [OK]

Common Mistakes:

• Not initializing dp array properly
• Ignoring dp[i - coin] == int.MaxValue check
• Confusing minimum with maximum coin count