Fibonacci Using DP in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci DP with memoization

What is the output of the following Java code that calculates the 7th Fibonacci number using memoization?

DSA Java

import java.util.Arrays;
public class Fibonacci {
    static int[] memo = new int[8];
    public static int fib(int n) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
    public static void main(String[] args) {
        System.out.println(fib(7));
    }
}

A 8

B 34

C 21

D 13

💡 Hint

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

The 7th Fibonacci number (starting from 0) is 13 if counting from zero index, but since fib(0)=0, fib(1)=1, fib(7) = 13 or 21 depending on indexing. Here fib(7) returns 13 if zero-based, but code uses fib(7) with base cases fib(0)=0 and fib(1)=1, so fib(7) = 13. However, memo array size is 8, so fib(7) is computed correctly as 13.

❓ Predict Output

intermediate

Output of Fibonacci DP with tabulation

What is the output of this Java code that calculates the 10th Fibonacci number using bottom-up tabulation?

DSA Java

public class FibonacciTab {
    public static int fib(int n) {
        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];
        }
        return dp[n];
    }
    public static void main(String[] args) {
        System.out.println(fib(10));
    }
}

A 144

B 55

C 89

D 34

💡 Hint

The 10th Fibonacci number starting from 0 is 55.

The code uses bottom-up DP to fill dp array. dp[10] = 55 because Fibonacci sequence is 0,1,1,2,3,5,8,13,21,34,55...

🔧 Debug

advanced

Identify the error in Fibonacci DP code

What error will this Java code produce when run?

DSA Java

public class FibonacciError {
    static int[] memo = new int[5];
    public static int fib(int n) {
        if (n <= 1) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
    public static void main(String[] args) {
        System.out.println(fib(7));
    }
}

A ArrayIndexOutOfBoundsException

B StackOverflowError

C NullPointerException

D No error, prints 13

💡 Hint

Check the size of the memo array and the index accessed.

The memo array has size 5, but fib(7) tries to access memo[7], causing ArrayIndexOutOfBoundsException.

🧠 Conceptual

advanced

Why use DP for Fibonacci?

Why is dynamic programming preferred over simple recursion for calculating Fibonacci numbers?

A DP avoids repeated calculations by storing results, improving efficiency

B DP uses less memory than recursion

C DP always uses less code than recursion

D DP can calculate Fibonacci numbers without any loops or recursion

💡 Hint

Think about how recursion repeats work.

Simple recursion recalculates the same Fibonacci numbers many times. DP stores results to avoid this, making it faster.

❓ Predict Output

expert

Output of optimized Fibonacci DP with space optimization

What is the output of this Java code that calculates the 15th Fibonacci number using space-optimized DP?

DSA Java

public class FibonacciOptimized {
    public static int fib(int n) {
        if (n <= 1) return n;
        int prev2 = 0, prev1 = 1, current = 0;
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
    public static void main(String[] args) {
        System.out.println(fib(15));
    }
}

A 377

B 987

C 610

D 1597

💡 Hint

The 15th Fibonacci number starting from 0 is 610.

The code uses two variables to store previous Fibonacci numbers, calculating fib(15) = 610.

Practice

1. What is the main advantage of using Dynamic Programming (DP) to calculate Fibonacci numbers compared to a simple recursive approach?

easy

A. It uses less memory by not storing any intermediate results.

B. It avoids repeated calculations by storing results of subproblems.

C. It calculates Fibonacci numbers using a closed-form formula.

D. It uses randomization to speed up the calculation.

Solution

1. Step 1: Understand recursive Fibonacci drawbacks

   Simple recursion recalculates the same Fibonacci numbers many times, causing inefficiency.

2. Step 2: How DP improves calculation

   DP stores results of smaller Fibonacci numbers to reuse them, avoiding repeated work.

3. Final Answer:

   It avoids repeated calculations by storing results of subproblems. -> Option B

4. Quick Check:

   DP stores subproblem results = avoids repeats [OK]

Hint: DP saves previous results to avoid repeated work [OK]

Common Mistakes:

• Thinking DP uses less memory than recursion
• Confusing DP with closed-form formulas
• Believing DP uses randomization

2. Which of the following Java code snippets correctly initializes the DP array for Fibonacci calculation of size n?

easy

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

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+1]; dp[0] = 0; dp[1] = 1;

Solution

1. Step 1: Determine array size for Fibonacci DP

   To store Fibonacci numbers up to n, array size must be n+1 to include index n.

2. Step 2: Check base cases initialization

   Fibonacci starts with dp[0] = 0 and dp[1] = 1, so these must be set correctly.

3. Final Answer:

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

4. Quick Check:

   Array size n+1 with dp[0]=0, dp[1]=1 = correct initialization [OK]

Hint: Array size must be n+1 to hold Fibonacci up to n [OK]

Common Mistakes:

• Using array size n instead of n+1
• Initializing dp[0] as 1 instead of 0
• Using array size n-1 causing index errors

3. What is the output of the following Java code snippet?

int n = 5;
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];
}
System.out.println(dp[n]);

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Calculate Fibonacci values up to n=5

   dp[0]=0, dp[1]=1 Then dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=5

2. Step 2: Output dp[5]

   The value at dp[5] is 5, so the output is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Fibonacci(5) is 5 by definition [OK]

Common Mistakes:

• Confusing index with Fibonacci value
• Calculating dp[5] as 8 (Fibonacci(6))
• Off-by-one errors in loop

4. Identify the error in the following Java code for Fibonacci using DP and select the correct fix:

int n = 6;
int[] dp = new int[n];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n]);

medium

A. Change array size to n+1 to avoid index out of bounds error.

B. Initialize dp[2] = 1 before the loop.

C. Change loop condition to i < n instead of i <= n.

D. Remove dp[0] initialization.

Solution

1. Step 1: Analyze array size and loop bounds

   Array dp has size n (6), but loop runs i from 2 to 6 inclusive, accessing dp[6] which is out of bounds.

2. Step 2: Fix array size to n+1

   Increasing array size to n+1 (7) allows dp[6] access without error.

3. Final Answer:

   Change array size to n+1 to avoid index out of bounds error. -> Option A

4. Quick Check:

   Array size n+1 fixes index error [OK]

Hint: Array size must cover max index used in loop [OK]

Common Mistakes:

• Ignoring index out of bounds exception
• Changing loop condition without fixing array size
• Unnecessary initialization of dp[2]

5. You want to calculate the 10th Fibonacci number using DP but with space optimization to use only two variables instead of an array. Which code snippet correctly implements this?

hard

A. int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } System.out.println(c);

B. int a = 0, b = 1; for (int i = 2; i <= 10; i++) { a = a + b; b = a; } System.out.println(b);

C. int a = 0, b = 1; for (int i = 2; i < 10; i++) { int c = a + b; a = b; b = c; } System.out.println(b);

D. int a = 1, b = 1; for (int i = 2; i <= 10; i++) { int c = a + b; a = b; b = c; } System.out.println(b);

Solution

1. Step 1: Understand space optimization for Fibonacci

   We only need last two Fibonacci numbers to calculate the next, so two variables plus one temp variable suffice.

2. Step 2: Check loop and initialization correctness

   Start with a=0, b=1 (F0 and F1), loop from 2 to 10 inclusive, update c = a+b, then shift a=b, b=c.

3. Step 3: Verify output

   After loop, c holds Fibonacci(10) = 55, which is printed.

4. Final Answer:

   int a = 0, b = 1, c = 0; for (int i = 2; i <= 10; i++) { c = a + b; a = b; b = c; } System.out.println(c); -> Option A

5. Quick Check:

   Two vars + temp, correct loop = Fibonacci(10) [OK]

Hint: Use two vars and update in loop to save space [OK]

Common Mistakes:

• Incorrect loop bounds causing off-by-one
• Wrong initial values for a and b
• Not updating variables in correct order